프로그래머스-거리두기 확인하기

import java.util.*;
class Solution {
    int[] dy = {0, 1, 0};  // y축 이동 방향
    int[] dx = {1, 0, -1}; // x축 이동 방향
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for(int i=0; i < places.length; i++){
            answer[i] = solve(places[i]);
        }
        return answer;
    }
    
    private int solve(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') { // 대기실 현재 면접자의 위치를 기반 BFS 탐색
                    int ans = bfs(place, i, j);
                    if(ans == 0) return 0;
                }
            }
        }
        return 1;
    }
    
    // BFS 탐색 수행하는 메소드
    private int bfs(String[] place, int y, int x){
        Queue<Pos> q = new LinkedList<>();
        boolean[][] visited = new boolean[5][5];
        q.add(new Pos(y, x));
        visited[y][x] = true;
        
        while(!q.isEmpty()){
            Pos c = q.poll();
            for(int i=0; i < dy.length; i++){
                int ny = c.y + dy[i];
                int nx = c.x + dx[i];
                int mhtDist = Math.abs(ny - y) + Math.abs(nx - x); // 맨해튼 거리 측정
                
                // 범위 벗어난 경우 / 맨해튼 거리가 2 초과인 경우 / 이미 방문된 경우 통과
                if(ny < 0 || ny >= 5 || nx < 0 || nx >= 5 || mhtDist > 2 || visited[ny][nx]) continue;
                
                visited[ny][nx] = true;
                if(place[ny].charAt(nx) == 'P') return 0;  // 다른 지원자가 있으면 위반
                else if(place[ny].charAt(nx) == 'X') continue; // 파티션이면 방문 불가
                else q.add(new Pos(ny, nx)); // 빈 책상이라면 다음 탐색을 위해 추가
            }
        }
        return 1;
    }
}
class Pos{
    int y;
    int x;
    public Pos(int y, int x){
        this.y=y;
        this.x=x;
    }
}