[프로그래머스 / Level2] 거리두기 확인하기 (Java)

문제 보기

사용한 것

• 대기실에서 거리두기를 제대로 하고있는지 확인하기 위한 BFS

풀이 방법

• 대기실마다 BFS해서 거리두기를 제대로 하고있는지 확인
• visited를 선언하고 'P'인(응시자) 좌표를 q1에 넣어줌
• q1에서 하나씩 꺼내어 q2에 저장하고 q2로 BFS 시작
• 꺼낸 뒤 visited true로
• 만약 현재 꺼낸 것이 이동했고, 'P'이면 거리두기가 제대로 지켜지지 않았으므로 0 return
• 만약 현재 꺼낸 것이 2칸 이동했다면 더 이상 거리두기 계산할 필요가 없으므로 continue
• 4 방향으로 영역에서 벗어나는지, 이미 방문했는지 확인
• 통과했으면 'X'는 칸막이라 계산할 필요 없으므로 아닌 경우에만 q2에 넣어줌
• 모든 while문 끝났으면 거리두기가 제대로 되고있으므로 1 return

코드

class Solution {

    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};

    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for (int i = 0; i < 5; i++) {
            answer[i] = bfs(places[i]);
        }

        return answer;
    }

    int bfs(String[] place) {
        boolean[][] visited = new boolean[5][5];
        Queue<int[]> q1 = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (place[i].charAt(j) == 'P') {
                    q1.offer(new int[]{i, j, 0});
                }
            }
        }

        Queue<int[]> q2 = new LinkedList<>();
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
            while (!q2.isEmpty()) {
                int[] cur = q2.poll();
                int x = cur[0];
                int y = cur[1];
                visited[x][y] = true;

                if (cur[2] != 0 && place[x].charAt(y) == 'P') {
                    return 0;
                }

                if (cur[2] == 2) {
                    continue;
                }

                for (int i = 0; i < 4; i++) {
                    int nx = cur[0] + dx[i];
                    int ny = cur[1] + dy[i];

                    if (!isOOB(nx, ny) && !visited[nx][ny]) {
                        if (place[nx].charAt(ny) == 'X') {
                            continue;
                        }

                        q2.offer(new int[]{nx, ny, cur[2] + 1});
                    }
                }
            }
        }

        return 1;
    }

    boolean isOOB(int x, int y) {
        if (x < 0 || x >= 5 || y < 0 || y >= 5) {
            return true;
        }

        return false;
    }
}