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

문제풀이 접근

1. 한번에 5개의 케이스가 주어지므로, places[]로 처음에 순회를 해야한다.

2. 배열에서 'P'를 찾으면, 해당 좌표를 bfs 돌려준다.

  2-1. 해당 좌표를 큐에 넣고, 방문 처리 해준다.

  2-2. 범위를 초과했거나, 방문한 지역이면 continue 해준다.

  2-3. 만약에 순회한 지역에서 'P'를 찾고, 거리가 2 이내라면 false를 리턴한다.

  2-4. 'O'이면서 거리가 2 이내일 때, 큐에 넣어서 탐색을 계속 이어나간다.

3. bfs의 결과를 flag에 반영하고, 그 결과에 따라서 answer 배열 값을 업데이트 해준다.

import java.util.*;
class Solution {
    static int [] dx = {1,0,-1,0};
    static int [] dy = {0,1,0,-1};
    static boolean [][] visited;
    static Queue<int []> queue;
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        int idx = 0;
        
        for(String [] place : places) {
            visited = new boolean[5][5];
            queue = new LinkedList<>();
            boolean flag = true;
            
            for(int i = 0; i < 5; i++){
                for(int j = 0; j < 5; j++) {
                    if (place[i].charAt(j) == 'P') {
                        if (!bfs(place,i,j)) {
                            flag = false;
                            break;
                        }
                    }
                }
            }
            if (flag) answer[idx++] = 1;
            else answer[idx++] = 0;
        }
        return answer;
    }
    
    public boolean bfs(String [] place, int i, int j) {
        visited[i][j] = true;
        queue.add(new int[]{i,j});
        
        while(!queue.isEmpty()) {
            int [] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            for(int dir = 0; dir < 4; dir++){
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
                if (visited[nx][ny]) continue;
                
                int dist = Math.abs(nx - i) + Math.abs(ny - j);
                // 가르키는 곳이 P이고 거리가 2이하면 false 리턴
                                
                if (place[nx].charAt(ny) == 'P' && dist <= 2) {
                    return false;
                }
                
                // 빈 자리이고, 거리가 2 이내일 때 다시 큐에 넣어서 돌린다.
                else if (place[nx].charAt(ny) == 'O' && dist <= 2) {
                    queue.add(new int[]{nx,ny});
                    visited[nx][ny] = true;
                }
            }
        }
        return true;
    }
}

 

문제풀이 회고

차근차근 생각한다면 딱히 어렵지 않았는데, 너무 많이 생각하느라 답을 참고했다.

 

까다로웠던 부분은, 빈자리 일 때, 큐에 넣어서 다시 탐색을 반복하는 건 알겠는데 거리가 2 이내 이부분이 많이 헷갈렸다.

 

 

위 예제를 참고할 때, (1,2) 지점에서 BFS를 돌린다고 가정하자.

 

일단 거리가 1인 지점에는 P가 없으니 계속 진행할 것이고 (0,2) 지점이 'O'이고, 거리도 2 이내니 큐에 넣어서 탐색을 다시 이어나가야 한다.

 

이제 (0,2)에서 탐색을 진행할때, (0,3)에서 거리가 2인 P가 있으므로 false를 리턴해야 한다.

 

주의점

• 해당 거리의 차이는 무조건 P에서 계산한다. (O에서 BFS를 돌렸더라도 거리 기준은 처음에 P가 된다.)
• 그래서 (1,2)와 (0,3)을 비교할 때, 거리가 2이므로 false를 리턴해준다!

 

이렇게 풀어서 쓰니 좀 이해가 되는데?