[프로그래머스] 거리두기 확인하기 (2021 카카오 채용연계형 인턴십)

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

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

2021-07-19

---

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class Solution81302 {
    public static Character[][] arr;
    public static boolean[][] vtd;
    public static Queue<int[]> q, f;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
 
    public static void init(String[][] places, int x) {
        for (int i = 0; i < 5; i++) {
            String tmp = places[x][i];
            for (int j = 0; j < 5; j++) {
                arr[i][j] = tmp.charAt(j);
                vtd[i][j] = false; // init
                if (arr[i][j] == 'P') f.add(new int[]{i, j}); // P
            }
        }
    }
 
    public static int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        arr = new Character[5][5];
        vtd = new boolean[5][5];
        q = new LinkedList<>();
 
        for (int i = 0; i < places.length; i++) {
            f = new LinkedList<>();
            init(places, i);
            boolean flag = false;
            loop:
            while (!f.isEmpty()) { // P를 기준으로
                int[] tmp = f.poll();
                int x = tmp[0];
                int y = tmp[1];
                q = new LinkedList<>();
                q.add(new int[]{x, y});
                vtd[x][y] = true;
                int count = 0;
                while (!q.isEmpty()) { // 2칸 이내로 체크
                    int size = q.size();
                    while (size > 0) { // 1, 2칸까지만 체크
                        int[] temp = q.poll();
                        int xx = temp[0];
                        int yy = temp[1];
 
                        for (int k = 0; k < 4; k++) {
                            int nx = xx + dx[k];
                            int ny = yy + dy[k];
 
                            if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || arr[nx][ny] == 'X') continue;
                            if (!vtd[nx][ny]) {
                                if (arr[nx][ny] == 'P') {
                                    flag = true;
                                    break loop;
                                } else {
                                    vtd[nx][ny] = true;
                                    q.add(new int[]{nx, ny});
                                }
                            }
                        }
                        size--;
                    }
                    count++;
                    if (count == 2) break;
                }
            }
            if (!flag) answer[i] = 1;
        }
 
        return answer;
    }
 
    public static void main(String[] args) {
        String[][] p = {
                {"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"},
                {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"},
                {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"},
                {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"},
                {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"},
        };
 
        System.out.println(Arrays.toString(solution(p)));
    }
}
 

#문제풀이

맨허튼 거리 2 이하면 거리두기가 지켜지지 않는 것인데, 예외 사항은 파티션이 있는 경우이다.

 

1. 해당 대기실의 P(응시자)를 배열을 만들때 먼저 queue에 넣어놓는다.

 

2. P를 하나씩 꺼내서, P주변의 4방향 칸들을 체크한다. 

 

3. P 주변의 칸에 X(파티션)이 있는 경우 그 쪽 부분은 더 이상 체크하지 않는다. 

 

4. O(빈 의자)가 있는 경우, 계속 체크한다.

 

5. 2~4번을 2번만 반복해서 실행한다. 그 안에 다른 P(응시자)를 만나면 거리두기가 지켜지지 않는 것이므로, 현재 대기실 탐색을 끝내고 다음 대기실을 탐색한다.