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

문제는 단순하게 볼수 있다.

 

문제 설명

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

대기실은 5개이며, 각 대기실은 5x5 크기입니다.
거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

 

해결법.

각 ‘P’에 대해:
맨해튼 거리 2 이내에서, 'O'는 거리<2일 때만 확장하며 탐색한다.
탐색 도중 다른 'P'를 만나면 즉시 위반.
'X'의 경우는 생각하지 않아도 된다고 판단 (만나면 그곳은 못지나가니까.)

 

코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];

        for (int i = 0; i < places.length; i++) {
            boolean ok = true;
            String[] p = places[i];

            out:
            for (int r = 0; r < 5; r++) {
                for (int c = 0; c < 5; c++) {
                    if (p[r].charAt(c) == 'P') {
                        if (bfs(r, c, p)) {
                            ok = false;
                            break out;
                        }
                    }
                }
            }

            answer[i] = ok ? 1 : 0;
        }
        return answer;
    }

    private static boolean bfs(int r, int c, String[] p){
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        Queue<int[]> q = new LinkedList<int[]>();
        q.offer(new int[]{r, c});

        while(!q.isEmpty()){
            int[] position = q.poll();

            for (int i = 0 ; i < 4 ; i ++){
                int nowR = position[0] + dr[i];
                int nowC = position[1] + dc[i];

                if (nowR < 0 || nowC < 0 || nowR >= 5 || nowC >= 5 || (nowR == r && nowC == c)) continue;
                int d = Math.abs(nowR - r) + Math.abs(nowC - c);

                if (d <= 2 && p[nowR].charAt(nowC) == 'P') return true;
                else if (d < 2 && p[nowR].charAt(nowC) == 'O') q.offer(new int[]{nowR, nowC});
            }
        }

        return false;
    }
}

 

 

회고

bfs라고 빠르게 접근 후 문제를 받아 드려서, 생각보다 빠르게 푼 감이 있다. 물론 중간중간 BFS 어떻게 만들더라는 생각이 있었지만... BFS 로직을 안까먹고 있어서 다행이다.