[BFS or 구현]프로그래머스 거리두기 확인하기 (풀이보충)

접근

거리두기 확인하기

저는 완전 구현 및 완전탐색 문제라고 생각하고 접근하였습니다.
문제에 주어지는 매개변수의 크기가 작았기 때문에
조건문을 통해 모든 대기실의 사람을 검사했습니다.

칸막이인 경우에는 검사를 하지 않았고
사람이 있는 경우와 칸막이가 없는 빈 책상인 경우에 검사를 실시했습니다.
사실 문제를 풀면서 저는 발생할 수 있는 모든 조건을 생각하여 구현하여 정답에 도달했지만

실제로 이런 문제에 대해서 위와 같이 모든 조건을 생각해내란 것을 보장할 수 없었습니다.
그래서 스터디원의 풀이를 참고하여 BFS로 접근한 풀이를 구현해보았습니다.

그림으로 정리해보았습니다.
위 그림의 전제조건은 현재 위치에 P가 있다는 전제하에 진행됩니다.
즉 BFS를 진행하기 위한 전제조건은 현재 위치에 P가 있다는 것입니다.

상하좌우로 나아가되, 1레벨과 2레벨을 분리하여 나아갑니다.
1레벨에 P가 있는 경우는 당연히 false입니다.
1레벨에 X가 있는 경우 넘어갑니다.
1레벨에 O가 있는 경우 Queue에 넣어 2레벨에서 검사를 진행합니다.

2레벨에 도달했다는 것은 1레벨에 O가 존재했다는 것입니다.
따라서 2레벨에 P가 존재하는 경우 false를 반환해야 합니다.

나의 풀이 (완전탐색)

class Solution {
    
    static char[][] room;
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        //오른쪽 아래 모두 칸막이 존재 그냥 넘어가기
        // 아닌 경우
        // 모두 아닌 경우 -1
        //오른쪽만 있는 경우 -> row +2 검사
        // 왼쪽만 있는 경우 -> col+2 검사
        
        for(int i=0;i<5;i++){
            room = new char[5][5];
            for(int j=0;j<5;j++){
                room[j]=places[i][j].toCharArray();
            }
            
            answer[i]=check(room);
            
            
        }
       
        return answer;
    }
    
    static int check(char[][] room){
        
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(room[i][j]=='P'){
                    if(i+1<=4 &&j+1<=4 && room[i+1][j]=='X'&& room[i][j+1]=='X') continue;
                    else if (i+1<=4 && j+1<=4 && room[i+1][j+1]=='P') return 0;
                    else if (i-1>=0  && j+1<=4 &&room[i][j+1]=='O'&& room[i-1][j+1]=='P') return 0;
                    else if((i+1<=4 && room[i+1][j]=='P')|| (j+1<=4 &&room[i][j+1]=='P')) return 0;
                    else if(i+2<=4 && room[i+1][j]=='O' && room[i+2][j]=='P') return 0;    
                    else if(j+2<=4 &&room[i][j+1]=='O'&& room[i][j+2]=='P') return 0;  
                }else if( room[i][j]=='O'){
                    if(i+1<=4 && j+1<=4 && room[i+1][j]=='X'&& room[i][j+1]=='X') continue;
                    if(i+1<=4 && j+1<=4 && room[i+1][j]=='P'&& room[i][j+1]=='P') return 0;
                    
                }
                
            }
        }
        
        return 1;    
        
    }
    
}

풀이 (BFS)

import java.util.*;

class Solution {
    
    static class Cost{
        int r;
        int c;
        int d;
        public Cost(int r, int c, int d){
            this.r=r;
            this.c=c;
            this.d=d;
        }   
    }
    
 
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        
        for(int i=0;i<5;i++){
            
            // 대기실 만드는 과정
            char[][] room = new char[5][5];
            for(int j=0;j<5;j++){
                room[j]=places[i][j].toCharArray();
            }
            
            boolean tag = false;
            for(int j=0;j<5;j++){
                for(int z=0;z<5;z++){
                // 현재 위치에 P가 있으면 BFS 진행
                    if(room[j][z]=='P'){
                       if(!bfs(j,z,room)){
                           tag=true;
                           
                       }
                    }
                }
            }
            
            answer[i]= tag==true? 0 :1;
            
            
        }
        
        
        return answer;
        
    }
    
    static boolean bfs(int row, int col, char[][] room){
        //상하좌우로 이동하기 위한
        int[] x = {-1,1,0,0};
        int[] y = {0,0,-1,1};
        
        
        Queue<Cost> q = new LinkedList<>();
        q.offer(new Cost(row,col,0));
        
        while(!q.isEmpty()){
            Cost c = q.poll();
            
            for(int i=0;i<4;i++){
                int newr = c.r+x[i];
                int newc = c.c+y[i];
                
                //여기서 중요한 것은 본인 위치로 다시 돌아오지 않도록 하는 조건문을 넣어줘야 합니다.
                if(newr<0 || newr>=5 || newc<0 || newc>=5 || (newr==row && newc==col)) continue;
                
                // 1레벨에 P가 있으면 false
                // 1레벨에 O인 경우 2레벨에 P가 있으면 false
                if(room[newr][newc]=='P' && c.d+1<=2) return false;
                
                //1레벨에 O가 있으면 Queue에 넣기
                if(room[newr][newc]=='O' && c.d+1<2){
                    q.offer(new Cost(newr,newc,c.d+1));
                }
                
                
                
                
            }  
        }
        return true;
         
        
    }
    
}