[프로그래머스][Level.2] 거리두기 확인하기

문제 풀이📝

BFS를 이용하여 풀었다.

• 5개의 대기실을 순회하면서 해당 대기실의 응시자들이 거리두기를 준수하는지 확인한다.
  • 응시자 기준 맨해튼 거리가 2를 넘는 칸들은 고려하지 않는다.
  • 맨해튼 거리가 2 이하일 때
    • 사람이 있고, 칸막이로 막혀있지 않은 경우라면 거리두기를 준수하지 못한 상태이다.

방문처리

• 응시자 기준 대각선 위치에 있는 칸은 두 번 방문할 수 있다! (초록색 참고)
• 나머지 칸들은 모두 한 번만 방문할 수 있도록 처리한다.

 

구현🛠️

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution_거리두기_확인하기 {

    private char[][][] rooms;

    private int[] dx = {-1, 0, 1, 0};
    private int[] dy = {0, -1, 0, 1};

    public int[] solution(String[][] places) {

        makeRoom(places);

        int[] result = new int[5];

        // 각 대기실마다
        for (int i = 0; i < 5; i++) {
            if (isValid(i)) {
                result[i] = 1;
            }
        }
        return result;
    }

    // String을 char 배열로 옮기기
    public void makeRoom(String[][] places) {

        rooms = new char[5][5][5];

        for (int k = 0; k < 5; k++) {
            for (int i = 0; i < 5; i++) {
                rooms[k][i] = places[k][i].toCharArray();
            }
        }
    }

    // 해당 대기실의 인원이 모두 거리두기를 준수했는지?
    public boolean isValid(int id) {

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                // 응시자가 있는 칸만 거리두기 준수 여부 확인
                if (rooms[id][i][j] != 'P') {
                    continue;
                }
                // 거리두기를 준수하지 못했다면 early return
                if (isFailed(id, i, j)) {
                    return false;
                }
            }
        }

        return true;
    }

    // 거리두기가 실패했는지 체크
    public boolean isFailed(int id, int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();
        int[][] visited = new int[5][5];
        q.offer(new int[]{x, y, 0, 'P'});
        visited[x][y]++;

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

            // 맨해튼 거리가 2를 넘는 애들은 확인할 필요가 없음
            if (cur[2] + 1 > 2) {
                continue;
            }

            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d];
                int ny = cur[1] + dy[d];
                if (isOutOfBounds(nx, ny)) {
                    continue;
                }
                // 응시자 기준 대각선 위치라면 -> 두 번까지 방문 가능
                if (visited[nx][ny] > (isDiagonal(x, y, nx, ny) ? 1 : 0)) {
                    continue;
                }

                // 사람이 있고, 칸막이로 막혀있지 않다면
                if (rooms[id][nx][ny] == 'P' && cur[3] != 'X'){
                    return true;
                }

                q.offer(new int[]{nx, ny, cur[2] + 1, rooms[id][nx][ny]});
                visited[nx][ny]++;
            }
        }
        return false;
    }

    public boolean isDiagonal(int x, int y, int nx, int ny) {
        if (Math.abs(x - nx) == 1 && Math.abs(y - ny) == 1) {
            return true;
        }
        return false;
    }

    public boolean isOutOfBounds(int x, int y) {
        if (x < 0 || x >= 5 || y < 0 || y >= 5) {
            return true;
        }
        return false;
    }
}

 

실행결과✅

테스트 1 〉	통과 (0.46ms, 76.2MB)
테스트 2 〉	통과 (0.21ms, 72.8MB)
테스트 3 〉	통과 (0.22ms, 76.1MB)
테스트 4 〉	통과 (0.18ms, 72.5MB)
테스트 5 〉	통과 (0.11ms, 77.4MB)
테스트 6 〉	통과 (0.17ms, 80MB)
테스트 7 〉	통과 (0.15ms, 72.5MB)
테스트 8 〉	통과 (0.21ms, 74.6MB)
테스트 9 〉	통과 (0.15ms, 73.8MB)
테스트 10 〉	통과 (0.11ms, 76.5MB)
테스트 11 〉	통과 (0.16ms, 75.5MB)
테스트 12 〉	통과 (0.15ms, 74.6MB)
테스트 13 〉	통과 (0.15ms, 79MB)
테스트 14 〉	통과 (0.17ms, 76.7MB)
테스트 15 〉	통과 (0.13ms, 75.9MB)
테스트 16 〉	통과 (0.20ms, 74.5MB)
테스트 17 〉	통과 (0.18ms, 75.7MB)
테스트 18 〉	통과 (0.14ms, 74.9MB)
테스트 19 〉	통과 (0.14ms, 76MB)
테스트 20 〉	통과 (0.20ms, 73.2MB)
테스트 21 〉	통과 (0.14ms, 76.4MB)
테스트 22 〉	통과 (0.22ms, 77MB)
테스트 23 〉	통과 (0.05ms, 78.7MB)
테스트 24 〉	통과 (0.07ms, 76.2MB)
테스트 25 〉	통과 (0.05ms, 79.2MB)
테스트 26 〉	통과 (0.06ms, 73.1MB)
테스트 27 〉	통과 (0.23ms, 73MB)
테스트 28 〉	통과 (0.20ms, 73MB)
테스트 29 〉	통과 (0.17ms, 67.4MB)
테스트 30 〉	통과 (0.15ms, 72.7MB)
테스트 31 〉	통과 (0.19ms, 73.9MB)