programmers_거리두기 확인하기_java

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

프로그래머스

import java.util.*;

class Solution {
     private static int[][] delta = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 상, 좌, 하, 우

    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        int idx = 0;
        for (String[] place : places){
            boolean res = isAllDistancing(place);
            if(res){ // 거리유지 잘 된경우
                answer[idx++] = 1;
            }else{
                answer[idx++] = 0;
            }
        }

        return answer;
    }

    // 해당 방이 거리유지를 지키고 있는지 확인
    public boolean isAllDistancing(String[] place){
        boolean res = true;

        int width = place[0].length();
        int height = place.length;

        for (int i = 0; i<height; i++){
            for (int j = 0; j<width; j++){
                if (place[i].charAt(j) == 'P'){ // 사람인 경우
                    if(!isDistancing(place, i, j, width, height)){
                        return false;
                    }
                }
            }
        }

        return res;
    }

    // 해당 위치가 거리유지를 지키고 있는지 확인
    public boolean isDistancing(String[] place, int y, int x, int width, int height){
        boolean res = true;

        Queue<int[]> queue = new LinkedList<>();
        int[] now = {y, x};
        queue.offer(now);

        boolean[][] visited = new boolean[height][width];
        int level = 2; // 멘하튼 거리가 2

        while (!queue.isEmpty()){
            int queueSize = queue.size();

            for (int i = 0; i<queueSize; i++){
                int[] nowPoint = queue.poll();

                if(visited[nowPoint[0]][nowPoint[1]]) continue;
                visited[nowPoint[0]][nowPoint[1]] = true;
                for (int j = 0; j<delta.length; j++){
                    int nexty = nowPoint[0] + delta[j][0];
                    int nextx = nowPoint[1] + delta[j][1];

                    if (0<=nexty && 0<=nextx
                            && nexty<height && nextx<width
                            && !visited[nexty][nextx]
                            && place[nexty].charAt(nextx) != 'X'){ // 파티션인경우 패스
                        if (place[nexty].charAt(nextx) == 'P'){ // 사람이 등장하는 경우
                            return false; // 거리 유지 실패
                        }
                        // 빈공간인 경우
                        int[] next = {nexty, nextx};
                        queue.offer(next);
                    }
                }
            }
            if(--level == 0) break;
        }

        return  res;
    }
}