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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/81302

참가자들이 맨해튼 거리가 2이하로 착석할 수 없지만, 파티션으로 격리되어 있다면 맨해튼 거리가 2이하여도 허용된다.
이는 특정 칸으로부터 2칸 이동을 해서 참가자를 만나면 안된다는 의미가 된다. 또, 파티션으로 막힌 곳은 이동할 수 없다는 상황과 동일해진다. 즉, 2차원 BFS 문제로 문제를 해결할 수 있다는 것이다.

문제 풀이 흐름

• 각 대기실에 대해 다음을 반복한다.

1. 참가자가 있는 자리를 시작점으로 BFS를 진행한다.
   1. 큐와 거리를 저장할 배열 distance를 준비하고, 시작점을 큐에 십입한 뒤 출발점 distance를 0으로 설정한다.
   2. 큐에서 현재 위치인 (x, y)를 꺼낸다.
   3. distance[y][x]가 2이상이면 B로 돌아가고, 그렇지 않다면 다음의 과정을 계속한다.
   4. dx, dy를 이용해 다음 위치인 (nx, ny)를 구한다.
   5. (nx, ny)에서 다음의 3가지 경우에 대해서는 D로 돌아가고, 이에 해당되지 않다면 다음의 과정을 반복한다.
      1. (nx, ny)가 정상 범위를 벗어난 경우
      2. (nx, ny)에 재방문 하는 경우
      3. (nx, ny)가 파티션인 경우
   6. 만약, (nx, ny)에 다른 참가자가 존재한다면 더 이상 진행하지 않고도 불가능함을 알 수 있으므로 false를 리턴하고 종료한다.
   7. 다른 참가자가 (nx, ny)에 없었다면, 해당 위치를 큐에 삽입하고 시작점으로부터의 거리를 기록한다.
2. BFS결과가 거짓이라면 배열에 0을, 참이라면 1을 저장한다.

import java.util.*;

class Solution {
    private static final int[] dx = {1, 0, -1, 0};
    private static final int[] dy = {0, 1, 0, -1};
    
    private static class Position {
        public final int x, y;
        
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    private int check(String[] place) {
        for (int i = 0; i < place.length; i++) {
            for (int j = 0; j < place[i].length(); j++) {
                if (place[i].charAt(j) != 'P') {
                    continue;
                }
                if (!bfs(place, new Position(j, i))) {
                    return 0;
                }
            }
        }
        return 1;
    }
    
    private boolean bfs(String[] place, Position start) {
        Deque<Position> dq = new LinkedList<>();
        int[][] distance = new int[5][5];
        for (int i = 0; i < distance.length; i++) {
            Arrays.fill(distance[i], -1);
        }
        dq.add(start);
        distance[start.y][start.x] = 0;
        
        while (!dq.isEmpty()) {
            int x = dq.peek().x, y = dq.peek().y;
            dq.pop();
            
            if (distance[y][x] >= 2) continue;
            
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5 
                    || distance[ny][nx] != -1 || place[ny].charAt(nx) == 'X') {
                    continue;
                }
                if (place[ny].charAt(nx) == 'P') return false;
                dq.add(new Position(nx, ny));
                distance[ny][nx] = distance[y][x] + 1;
            }
        }
        return true;
    }
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = check(places[i]);
        }
        return answer;
    }
}