[프로그래머스/BFS] 2021 카카오 인턴십 - 거리두기 확인하기

  [프로그래머스] 2021 카카오 인턴십- 거리두기 확인하기

안녕하세요, 오늘은 프로그래머스에서 카카오 인턴십 "거리두기 확인하기"를 풀어보았습니다.

예전부터 풀려고 노력했으나 BFS/DFS 개념이 확립되지 않은 상태로 풀려고 하니까 시간도 오래걸리고 헷갈려서

잠깐 보류했던 문제였습니다.

백준에서 BFS/DFS 개념을 숙달하고 풀이해보니까 확실히 쉽게 풀 수 있었던 것 같습니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

 

풀이 방법

• BFS를 사용해서 문제를 풀었습니다.
• P(사람)의 좌표를 따로 저장해, ArrayList에 저장하였고 list size만큼 for문을 돌아 list의 사람 좌표를 큐에 저장했습니다.
• 사람 좌표를 기준으로 bfs를 실시해 거리가 2 이하인데 다른 사람이 발견되면 for문 탈출해서 false 반환, 발견이 안되면 그대로 true를 반환되도록 했습니다.
• 핵심은, 사람의 좌표를 list에 저장한 것과 한번 거리를 이동할때마다 distance+1되어 distance<=2 일 때, 사람이 있는지 없는지 체크해주면 됩니다.

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Node{
    int a, b;
    int distance;
    Node(int a, int b, int distance){
        this.a = a;
        this.b = b;
        this.distance = distance;
    }
    public void setDistance(int distance){
        this.distance = distance;
    }
    public int getA(){
        return a;
    }
    public int getB(){
        return b;
    }
    public int getDistance(){
        return distance;
    }
}

public class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static String[][] map;
    static boolean[][] visit;
    static ArrayList<Integer> distance = new ArrayList<>();

    static public int[] solution(String[][] places) {
        int a = places[0].length;
        int b = places[0][0].length();
        for(int i = 0; i < a; i++){
            char[][] place = new char[a][b];
            for(int j = 0; j < b; j++) {
                    place[j] = places[i][j].toCharArray();
            }
            bfs(place);
        }
        int[] answer = distance.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
    static public void bfs(char[][] place) {
        boolean check = true;
        int n = place.length;
        int m = place[0].length;
        ArrayList<Node> people = new ArrayList<Node>(); // 사람이 앉아있는 좌표 저장
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (place[i][j] == 'P')
                    people.add(new Node(i, j, 0));
            }
        }
        Queue<Node> q = new LinkedList<>();
        loop:
        for (int i = 0; i < people.size(); i++) {
            visit = new boolean[n][m];
            q.offer(people.get(i));
            while (!q.isEmpty()) {
                Node node = q.poll();
                int x = node.getA();
                int y = node.getB();
                visit[x][y] = true;
                for (int j = 0; j < 4; j++) {
                    int a = x + dx[j];
                    int b = y + dy[j];
                    int distance = node.getDistance()+1;
                    if (a >= 0 && a < n && b >= 0 && b < m) {
                        if(visit[a][b] == true)
                            continue;
                        if(place[a][b] == 'X') // 벽일 때
                            continue;
                        if(place[a][b] == 'P' && distance <= 2){ // 거리두기가 안지켜 졌을 때
                            check = false;
                            break loop;
                        }else if(distance <= 2){
                            q.offer(new Node(a, b, distance));
                        }
                    }
                }
            }
        }
        if(check){
            distance.add(1);
        }else{
            distance.add(0);
        }
    }
}