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

📌 핵심 요약

• 각 P에서 BFS를 시작 — 맨해튼 거리 2 이내에 다른 P가 있는지 확인한다
• X는 벽으로 처리 — 파티션으로 막힌 경로는 큐에 넣지 않으므로 자연스럽게 걸러진다
• 거리 2에서 확장 중단 — dis == 2인 노드는 검사만 하고 이웃을 큐에 넣지 않는다

 

목차

Programmers #81302

거리두기 확인하기

5×5 대기실 5개 · P(응시자) / O(빈 자리) / X(파티션)

난이도: Lv.2

5×5 크기의 대기실 5개가 주어진다. 응시자들이 앉은 자리(P) 사이의 맨해튼 거리가 2 이하이면 거리두기 위반인데, 예외적으로 두 자리 사이가 파티션(X)으로 막혀 있으면 위반이 아니다. 각 대기실이 거리두기를 지키고 있으면 1, 아니면 0을 배열에 담아 반환한다.

풀이 과정

1. 대기실 5개를 각각 독립적으로 검사한다. 하나라도 위반 쌍이 발견되면 그 대기실은 0이다.
2. 대기실 안의 모든 P를 찾아, 각 P를 시작점으로 BFS를 돌린다.
3. BFS 도중 거리 1~2 위치에서 다른 P를 만나면 즉시 위반으로 판정한다. X는 큐에 넣지 않으므로 파티션으로 막힌 경로는 탐색되지 않는다.

1 접근 방법 — 왜 BFS인가

이 문제의 핵심은 “맨해튼 거리 2 이하”와 “파티션으로 막혀 있으면 예외”라는 두 조건을 동시에 처리하는 것이다.

단순히 좌표 차이로 맨해튼 거리만 계산하면 파티션 조건을 반영할 수 없다.

예를 들어 P X P처럼 두 응시자가 한 칸 건너 앉아 있어도, 사이에 파티션이 있으면 거리두기 위반이 아니다.

그래서 좌표 계산 대신 실제로 이동 가능한 경로 기준의 거리를 재기로 했다. X를 벽으로 취급하고 O와 P만 지나갈 수 있는 격자에서 BFS를 돌리면, 각 칸까지의 거리는 “파티션을 우회해서 도달하는 최단 거리”가 된다. 이 거리가 2 이하인 위치에 다른 P가 있을 때만 위반으로 판정하면 두 조건이 한 번에 해결된다.

💡

BFS의 최단 거리 보장이 핵심

BFS는 각 칸에 항상 최단 거리로 먼저 도달한다. P X P 케이스에서 오른쪽 P까지의 BFS 거리는 파티션을 우회한 3 이상이 되므로, 거리 2 이내 검사에 걸리지 않고 자연스럽게 통과 처리된다. 별도의 예외 분기 없이 파티션 조건이 해결되는 이유다.

2 BFS 설계

큐에 담는 상태

큐에는 {row, col, dis} 세 값을 담았다.

거리(dis)는 노드마다 달라지는 값이므로 큐 안에 함께 넣어 관리한다. 시작점의 거리는 0이고, 이웃으로 확장할 때마다 dis + 1로 넣는다.

위반 판정과 탐색 범위 제한

큐에서 노드를 꺼냈을 때 두 가지를 검사한다.

• 위반 검사 — dis > 0이면서 현재 칸이 P라면 거리 2 이내에 다른 응시자가 있다는 뜻이므로 false를 반환한다. dis > 0 조건은 시작점 자신(P)을 제외하기 위한 것이다.
• 확장 중단 — dis == 2라면 검사만 하고 이웃을 큐에 넣지 않는다. 거리 3 이상은 어차피 위반 대상이 아니므로 탐색할 필요가 없다.

확장 조건은 네 가지를 모두 만족해야 한다. 격자 범위 안이고, 방문하지 않았고, X(파티션)가 아닌 칸만 큐에 넣는다.

⚠️

경계 검사는 배열 접근보다 먼저

next_row >= 0 && next_row < 5 같은 범위 검사를 visited[next_row][next_col] 배열 접근보다 앞에 두어야 한다. 순서가 뒤집히면 격자 밖 좌표로 배열에 접근해 ArrayIndexOutOfBoundsException이 발생한다. && 연산자의 단축 평가(short-circuit) 덕분에 앞 조건이 false면 뒤 조건은 평가되지 않는다.

3 전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, 1, -1};

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

        for (int i = 0; i < places.length; i++) {
            answer[i] = check(places[i]) ? 1 : 0;
        }

        return answer;
    }

    public boolean check(String[] place) {
        char[][] arr = new char[5][5];

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                arr[i][j] = place[i].charAt(j);
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (arr[i][j] == 'P') {
                    if (!bfs(arr, i, j)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public boolean bfs(char[][] arr, int startRow, int startCol) {
        ArrayDeque<int[]> deque = new ArrayDeque<>();
        boolean[][] visited = new boolean[5][5];
        deque.add(new int[]{startRow, startCol, 0});
        visited[startRow][startCol] = true;

        while (!deque.isEmpty()) {
            int[] cur = deque.poll();
            int row = cur[0];
            int col = cur[1];
            int dis = cur[2];

            if (dis > 0 && arr[row][col] == 'P') {
                return false;
            }

            if (dis == 2) continue;  // 거리 2에서는 더 확장하지 않음

            for (int i = 0; i < 4; i++) {
                int nextRow = row + dr[i];
                int nextCol = col + dc[i];

                if (nextRow >= 0 && nextCol >= 0 && nextRow < 5 && nextCol < 5
                        && !visited[nextRow][nextCol] && arr[nextRow][nextCol] != 'X') {
                    visited[nextRow][nextCol] = true;
                    deque.add(new int[]{nextRow, nextCol, dis + 1});
                }
            }
        }

        return true;
    }
}

4 정리하면서 손본 부분

처음 제출한 코드도 정답이었지만, 정리하면서 몇 군데를 다듬었다.

불필요한 탐색 제거

처음 코드는 dis == 2인 노드에서도 이웃을 큐에 넣고, 꺼낸 뒤에야 if (dis > 2) continue로 버리는 구조였다.

정답에는 영향이 없지만 거리 3짜리 노드를 만들었다가 버리는 낭비가 있었다. dis == 2 시점에 확장을 멈추도록 바꾸면 거리 3 이상인 노드가 아예 생성되지 않는다.

이렇게 바꾸고 나니 위반 검사 조건도 단순해졌다. 원래는 dis > 0 && dis <= 2 && arr[row][col] == 'P'였는데, 큐에 거리 0~2인 노드만 들어오게 되면서 dis <= 2가 항상 참이 되어 조건에서 뺄 수 있었다.

구분	처음 코드	수정 후
확장 중단	dis > 2인 노드를 꺼낸 뒤 continue	dis == 2에서 확장하지 않음 개선
위반 검사	dis > 0 && dis <= 2 && P	dis > 0 && P 단순화
거리 3 노드	생성 후 폐기	생성되지 않음

스타일 정리

• answer[i] 대입을 if/else 대신 삼항 연산자 check(places[i]) ? 1 : 0으로 줄였다.
• 배열 선언을 int dx[]에서 Java 관례에 맞는 int[] dr 형태로 바꿨다. 이름도 행/열 의미가 드러나도록 dr/dc로 정했다.
• 변수명을 start_row → startRow처럼 카멜케이스로 통일했다.

ℹ️

조건문으로 직접 확인하는 대안도 있다

거리 제한이 2로 고정이라, BFS 없이 각 P 기준으로 “거리 1 상하좌우 / 거리 2 직선 / 대각선” 케이스를 조건문으로 직접 검사하는 풀이도 널리 쓰인다. 다만 케이스 분기가 많아 실수 여지가 있고, BFS 방식은 거리 제한이 바뀌어도 그대로 통용되는 일반적인 형태라 이 방식을 택했다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.