[프로그래머스] 거리두기 확인하기 - java

프로그래머스: 거리두기 확인하기

풀이

• 순차적으로 탐색하다 P를 만나면, 해당 P가 규칙을 어겼는지 확인한다.
• P를 기준으로 맨해튼 거리가 2이하인 자리들을 포함하면 위의 사진과 같다.
• 따라서 BFS를 돌며 P의 주위를 탐색한다.

  • 거리가 “2”인 자리는 반드시 “1”인 자리를 거쳐서 이동하는 것을 알 수 있다. (상, 하, 좌, 우 이동만 있다고 가정)

    👉 따라서 큐를 통해서 넘어온 자리 + P라면 무조건 false return한다. (주변이 파티션으로 막혀있었다면 어차피 도달 못했음)
    

  • 만약 해당 자리가 맨해튼 거리 1 이하이고 빈 자리라면 queue에 넣어준다.

    while (!q.isEmpty()) {
        int[] now = q.poll();
    
        for (int i = 0; i < 4; i++) {
            int nx = now[0] + dx[i];
            int ny = now[1] + dy[i];
            int dist = Math.abs(x - nx) + Math.abs(y - ny);
            if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || dist > 2 || visited[nx][ny]) continue;
    
            if (place[nx].charAt(ny) == 'P') return false; 
            if (dist <= 1 && place[nx].charAt(ny) == 'O') {
                visited[nx][ny] = true;
                q.offer(new int[]{nx, ny});
            }
        }
    }

전체 코드

import java.util.*;
class Solution {
    String[] place;
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        for (int i = 0; i < places.length; i++) {
            place = places[i];
            answer[i] = check() ? 1 : 0;
        }
        return answer;
    }

    public boolean check() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (place[i].charAt(j) == 'P') {
                    if (!bfs(i, j)) return false;
                }
            }
        }
        return true;
    }

    public boolean bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        boolean[][] visited = new boolean[5][5];
        visited[x][y] = true;

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

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                int dist = Math.abs(x - nx) + Math.abs(y - ny);
                if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || dist > 2 || visited[nx][ny]) continue;

                if (place[nx].charAt(ny) == 'P') return false;
                if (dist <= 1 && place[nx].charAt(ny) == 'O') {
                    visited[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return true;
    }
}