[프로그래머스_Lv.2] 거리두기 확인하기 (완전탐색+BFS _ JAVA)

 

BFS 문제 중에

가장 어렵게 푼 문제같다.

 

진짜 코딩테스트 문제였다면,

예시만 맞고 다 틀렸을 수도 있다..

 

 

---

문제

 

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

프로그래머스

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 완전 탐색 + BFS

 

 

풀이과정

1.

2차원 배열의 places를 반복문을 돌면서 하나의 배열씩 BFS를 돌린다.

 

2.

BFS안에서 queue를 생성하고, 매개변수로 받은 String[] 배열을 2차원 배열로 변경한다.

 

3.

반복문을 돌면서 map에서 응시자 표시인 P를 찾는다. 이때 반복문을 Loop로 지정한다.

그 좌표를 큐에 넣고, 방문체크를 한다.

 

4.

큐에서 좌표를 꺼낸 후, 사방탐색을 한다.

파티션이 있을 때는 더이상 탐색하지 못하므로 continue한다.

다른 응시자인 'P'를 발견했는데 depth의 크기가 2보다 크다면, 거리두기를 지킨 것이므로 continue한다.

다른 응시자인 'P'를 발견했는데 depth의 크기가 2보다 작다면 거리두기를 지키지 않을 것이므로, 더이상 탐색할 필요가 없으므로 상위 반복문인 Loop 반복문을 멈추고 0을 리턴한다.

빈테이블인 'O'이라면, 현재 좌표와 depth+1를 큐에 넣고 방문체크를 한다.

 

5.

거리두기가 지켜졌다면, 다시 Loop 반복문으로 돌아와서 P를 찾고 4번을 반복한다.

 

6.

BFS메서드에서 반환한 값인 0 또는 1를 answer에 저장하고 반환한다.

 

 

---

코드

 

import java.util.*;

class Solution {
    
    static int n;
    static int[] r, c;
    static boolean[][] isvisited;
    
    public int[] solution(String[][] places) {
        
        n = 5;
        
        r = new int[] {-1, 0, 1, 0};
        c = new int[] {0, 1, 0, -1};
        
       
        
        int[] answer = new int[n];
        for(int i=0; i<n; i++){
            answer[i] = BFS(places[i] , i);    
        }
        
        return answer;
    }
    
    //BFS
    public int BFS(String[] place, int idx){
        Queue<int[]> queue = new LinkedList();
        
        
        //2차원 배열로 변경
        String[][] map = new String[n][n];
        for(int i=0; i<map.length; i++){
            map[i] = place[i].split("");
        }
        
        boolean isCorrect = true;
            
        //P좌표를 queue에 넣기
        Loop:
        for(int i=0; i<map.length; i++){
            for(int j=0; j<map[i].length; j++){
                if(map[i][j].equals("P")) {
                    isvisited = new boolean[n][n];
                    
                    queue.add(new int[] {i, j, 1});
                    isvisited[i][j]=true;
                    
                    while(!queue.isEmpty()){
                        int[] cur = queue.poll();

                        int depth = cur[2];
                        
                        for(int k=0; k<4; k++){
                            int dr = cur[0]+r[k];
                            int dc = cur[1]+c[k];

                            if(!(0<=dr && dr<n && 0<=dc && dc<n)) continue;

                            //파티션이 있는 경우
                            if(map[dr][dc].equals("X")) continue;

                            //거리두기를 지킨 경우
                            if(map[dr][dc].equals("P") && 2<depth) continue;

                            //거리두기를 지키지 않은 경우
                            if(map[dr][dc].equals("P") && depth<=2 && !isvisited[dr][dc]) {
                                isCorrect = false; 
                                break Loop;
                            } 

                            //계속 탐색하는 경우
                            if(map[dr][dc].equals("O") && !isvisited[dr][dc]){
                                queue.add(new int[] {dr, dc, depth+1});
                                isvisited[dr][dc]=true;
                            } 
                        }
                    }
                }
            }
        }

         //반환값
        if(!isCorrect) return 0;
        else return 1;
        
    }
}