[프로그래머스][JAVA] 거리두기 확인하기 (DFS)

DFS인데 재귀로 안풀고 그냥 체크하는 방식으로 했음

조건절중 if문 가장 마지막 1칸 아래, 1칸 왼쪽을 체크 안해줘서 테케 3개인가 틀림

 

어떠한 자리 P를 기준으로 맨해튼 거리가 2이하인 점은 아래 그림과 같은데 

DFS로 처리하면 아래 점들을 모두 체크하지만 점 P를 기준으로 대칭되어 있는 점은 체크할 필요가 없기 때문에

수행시간을 반으로 줄일 수 있음 근데 파란 부분 점들만 체크하고 빨간점 중 둘 중 1개를 체크해줘야

 

맨해튼 거리가 2이하인 점들을 모두 체크할 수 있는 건데 저 빨간 부분을 체크안해줘서 틀림..

 

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        for(int i=0; i<places.length; i++){
            answer[i] = checkDistancing(places[i]);
        }
        
        return answer;
    }
    
    private int checkDistancing(String[] place){
        char[][] waitRoom = new char[7][7];
        for(int i=0; i<place.length; i++){
            // System.out.println(place[i]);  
            waitRoom[i] = (place[i]+"OO").toCharArray();
        }
        waitRoom[5] = "OOOOOOO".toCharArray();
        waitRoom[6] = "OOOOOOO".toCharArray();
        // System.out.println();
        
        // for(int i=0; i<waitRoom.length; i++){
        //     for(int j=0; j<waitRoom[0].length; j++){
        //         System.out.print(waitRoom[i][j]+" ");
        //     }
        //     System.out.println();  
        // }
        // System.out.println();  
        
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                // P 주변에 거리두기가 제대로 되어있는지 체크
                if(waitRoom[i][j]=='P'){
                    // System.out.println(i+" "+j);
                    if(waitRoom[i+1][j]=='P')   // 1칸 아래
                        return 0;
                    if(waitRoom[i][j+1]=='P')   // 1칸 오른쪽
                        return 0;
                    if(waitRoom[i+2][j]=='P' && waitRoom[i+1][j]=='O') // 2칸 아래 칸막이 없음
                        return 0;
                    if(waitRoom[i][j+2]=='P' && waitRoom[i][j+1]=='O') // 2칸 오른쪽 칸막이 없음
                        return 0;
                    if(waitRoom[i+1][j+1]=='P' && (waitRoom[i+1][j]=='O' || waitRoom[i][j+1]=='O')){
                        return 0;
                    }
                    if(j-1>=0 && waitRoom[i+1][j-1]=='P' && (waitRoom[i][j-1]=='O' || waitRoom[i+1][j]=='O')){
                        return 0;
                    }
                    
                }
            }  
        }
        
        return 1;
    }
}​