프로그래머스 (카카오) | LV.2 거리두기 확인하기 - BFS 문풀 (Java)

⬛ 프로그래머스 (카카오) | LV.2 거리두기 확인하기 - BFS 문풀 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

문제 설명

---

💚문제 접근 방식

처음에는 P를 갖는 x,y 좌표들을 모두 pQ에 담아서 경우의 수에 따라 처리를 하려고 했다.

조건이라 함은 맨허튼 거리를 모든 P간에 구해두고, 현재 P위치에서 맨허튼 거리 2이하의 좌표 사이에서 파티션 존재유무를 확인하면 되지 않을까 했는데, 이렇게 시도하다가 실패헀다.. 풀이를 찾아보고 이해한 내용을 토대로 작성했다.

→ BFS를 매번 P 좌표 기준으로 호출하면서 조건에 어긋나는 케이스가 하나라도 존재하면 0을 모두 만족하면 1을 반환하도록 하는 풀이를 봤다. 깔끔해보여서 이를 참고했다.

 

1) places배열을 순회하면서 P가 발견되는 좌표에 대해 BFS 탐색을 시도한다.

 

2) 4방향으로 탐새시도할 건데, 매번 호출된 P의 고정 위치를 기준으로 BFS탐색을 4방향으로 뻗어가며 조건을 판별한다.

• 1 이내의 값이 O인 경우 Q에 다시 담아서 더 탐색을 시도할텐데 만약 파티션이 있어서 X가 존재한다면 이 경우는 큐에 담기지 않고 넘어가도록 한다.
• 이런 BFS 순회를 Q가 빌 때까지 하다가 인접한 2이내의 P가 존재하지 않아서 모두 순회하고 나면 최종 false (조건에 맞음) 로 반환되어 이 격자판에 문제가 없음을 알린다.
• 그럼에도 맨허튼 거리 2이내의 값인 P가 나타날 경우 조건에 어긋나고 반환된다. (true - 조건어긋남)

 

3) 탐색 범위 벗어나는 곳은 제외시키며 이 방식을 반복하게 되면 규칙에 어긋나는 케이스에 대한 답을 세팅하여 최종 정답 처리가 된다.

 

💚 제출 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
    //BFS 함수 
    static boolean bfs(int x, int y, String[] p) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

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

        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = temp[0] + dx[i];
                int ny = temp[1] + dy[i];

                // 탐색 범위를 벗어나면 + 최초 출발점을 탐색에서 제외
                if ((nx < 0 || ny < 0 || nx >= 5 || ny >= 5) || (nx == x && ny == y)) continue;

                // 맨해튼 거리 구하기
                int m = Math.abs(x - nx) + Math.abs(y - ny);

                // p가 맨해튼 거리 안에 있다면
                if (p[nx].charAt(ny) == 'P' && m <= 2) {
                    return true;
                // O를 발견했는데 m 1이하이면 O를 중심으로 다시 탐색한다. 
                    //만약 빈 자리가 아니라 파티션이 존재할 경우 Q에 안담기고 계속 순회하니까 파티션 있으면 false를 반환하게 된다.
                } else if (p[nx].charAt(ny) == 'O' && m < 2) {
                    queue.add(new int[]{nx, ny});
                }
            }
        }
        return false;
    }    
    
    //솔루션 함수 
    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        for (int i = 0; i < places.length; i++) {
            String[] temp = places[i];
            boolean check = false;
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    if (temp[j].charAt(k) == 'P') {
                        if(bfs(j, k, temp)) {
                            check = true;
                        }
                    }
                }
            }
            answer[i] = check ? 0 : 1;
        }
        return answer;
    }
}