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

 

문제 파악

-저번 실습으로 나온 문제. 각 방을 돌며 최초의 좌석 찾고 그로부터 되는 방향을 나아가며 거리가 2 이내에 좌석이 발견되면 false리턴

• places의 행 길이(대기실 개수) = 5
• places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
• places 원소의 길이(대기실 가로 길이) = 5
• P는 응시자가 앉아있는 자리를 의미합니다.
• O는 빈 테이블을 의미합니다.
• X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
• 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
• places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
• 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

 

접근 방법

-저번엔 DFS로 풀이했었는데 이번엔 BFS로 접근해보기.

-방이 여러개여서 3차원 배열로 해야하나 고민했지만, bfs를 따로 빼는 방법이 있음

-각 방마다 true/false 판별 시 도중에라도 리턴받아 1 또는 0 배열에 기록

-*거리가 2일 때는 더 이상의 순회를 하지 않고 continue로 이어감

-그 전까지 자리가 나오면 거리두기 안지킨 것이므로 바로 false

-큐에 넣을 때 조건 체크하여 넣기 (범위를 벗어나지 않는지, 방문 여부, 파티션 여부- 파티션이면 벽으로 간주하여 순회하지X) + 방문 여부 업데이트

-큐에서 빼서는 좌석인지 아닌지, 여부만 판단

 

코드 구현

import java.util.*;

class Solution {
    public int[] solution(String[][] places) {
        int rooms = places.length;
        int[] result = new int[rooms];
        
        Arrays.fill(result,1);
        
        for(int k=0;k<rooms;k++){
           if(!checkRooms(places[k])){
               result[k]=0;
           }
        }
        
        
        return result;
    }
    public boolean checkRooms(String[] room){
        int row=room.length;
        int col=room[0].length();
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(room[i].charAt(j)=='P'){
                    if(!bfs(i,j,room,row,col)){
                        return false;
                    }
                }
            }
        } 
        return true;
    }
    
    public boolean bfs(int x,int y,String[] room,int row,int col){
        //동서남북
        int[] toX = {-1,1,0,0};
        int[] toY = {0,0,-1,1};
        Queue<int[]> que = new ArrayDeque<>();
        boolean[][] visited = new boolean[row][col];
        que.offer(new int[]{x,y,0});
        visited[x][y]=true;
        while(!que.isEmpty()){
            int[] node=que.poll();
            int qx=node[0];
            int qy=node[1];
            int ql=node[2];
            
            if(ql>0 && room[qx].charAt(qy)=='P'){
                return false;
            }
            if(ql>=2) continue;

            for(int i=0;i<4;i++){
                int dx=qx+toX[i];
                int dy=qy+toY[i];
                if(dx>=0&&dx<row&&dy>=0&&dy<col&&!visited[dx][dy]){
                    if(room[dx].charAt(dy)!='X'){
                        que.offer(new int[]{dx,dy,ql+1});
                        visited[dx][dy]=true;
                    }
                }
            }
            
        }

        return true;
    }
}

 

배우게 된 점

-bfs는 따로 함수를 빼 본 적이 없어서 조금 헷갈리는 부분이 있었지만,

함수로 빼니 복잡한 로직이 단순하게 정리가 되었다.

분명히 풀었던 문제이지만 익숙해지니 왜 문제가 생겼는지 오히려 판단이 어려웠음

뭐가 뭔지 스스로 설명하며 막힘없이 코드를 작성할 수 있을 때까지 연습이 필요할 것 같다.