LV2. 거리두기 확인하기(2021 카카오 인턴십)

😁접근 방법

첫 번째로 든 생각은 각각의 대기실을 기준으로 (0,0)부터 5X5크기의 행렬을 완전 탐색하며 P(면접자가 있는 곳) 를 만나게 되면

1. P를 기준으로 거리가 1이라면 P가 있는지
2. 1번에 해당이 안되면 거리가 2인지점을 탐색하여 파티션이 없는데 P인 지점이 있는지 확인.
3. 2번 경우도 아니라면, 대각선에 P가 있는데 그 사이가 파티션 2개가 없는경우인지 확인
4. 만약 모든 P지점에 대하여 1,2,3번의 경우가 다 아니라면 해당 대기실은 문제가 없는것.

위와 같은 알고리즘으로 완전 탐색을 하는 것이다. 우선 index를 아주 많이 건드려야 하고 그 구현도 매우 복잡할 것 같아 다른 방법을 생각해 보았다.

두 번째는 BFS를 이용하는 것이다. 문제를 잘 해석하면 P를 기준으로 맨해튼 거리가 2이하인 지점에 또다른 P가 있으면 안된다는 것이 가장 큰 기준인 것을 알 수 있는데, 이를 통해 P를 기준으로 가까운 자리(단, 파티션인 지점은 갈 수 없다.)부터 탐색하며 조건을 판단해야겠다는 생각을 하였다.

BFS구현이 잘 생각이 나지 않아서 다시 공부를 하고 풀게되었다.

기본적인 BFS구현 틀을 기준으로, 문제에서 설명한 조건들을 잘 추가해주며 BFS를 구현하였다.

😁나의 코드

Queue를 구현할 때 Queue의 클래스를 Point를 사용하도록 정의하였다. 원래 자바에 기본적으로 있는 Point클래스는 (x,y)좌표를 표현하지만, 나는 현재 P로부터의 거리를 나타내는 dist변수를 추가하여 재정의하였다!

코드에 주석을 다 달아놓아서 읽어보며 이해하면 될 것!

import java.util.*;

class Point{ //자바에서 기본제공되는 Point클래스가 있지만, 거리의 정보까지 추가해주기 위해 재정의 하였다.
    Point(int r, int c, int d){ //Point클래스의 생성자
        row=r;
        col=c;
        dist=d;
        
    }
    int row;
    int col;
    int dist;
}



class Solution {
    int [][] mv =  {{-1,0}, {1,0}, {0,-1}, {0,1}};//행렬에서 상하좌우 이동 할때, row와 col의 동작을 표시!
    public int[] solution(String[][] places) {
        int[] answer = new int [5];
        
        
        for(int i=0;i<5;i++){
            if(check(places[i])){
                answer[i]=1;
            }
            else {
                answer[i]=0;
            }
        }
        
        return answer;
    }
    
    public boolean check(String [] place){
        for(int r=0;r<5;r++){
            for(int c=0;c<5;c++){
                if(place[r].charAt(c)=='P'){
                    if(bfs(place, r, c)==false){
                        return false;
                    }
                }
                
            }
        }
        return true;
    }
    
    public boolean bfs(String [] place, int row, int col){
        boolean[][] visited = new boolean[5][5];
        
        Queue<Point> q = new LinkedList<>();
        
        visited[row][col]=true;
        q.add(new Point(row, col, 0));//시작위치는 P로부터의 거리가 0이다. P에서 시작하니까!!
        
        while(!q.isEmpty()){
            Point v = q.remove();
            
            if(v.dist>2){
                continue; //현재 위치로부터 거리가 2보다 크면 그냥 skip함.
            }
            if(v.dist!=0 && place[v.row].charAt(v.col)=='P'){
                return false; //거리두기를 지키지 않는 경우
            }
            //위의 두 경우가 아니다. 그러므로 이제 이동하여 새로운 탐색 시작
            //상하좌우 일때, bfs를 탐색해야한다.
            for(int i=0;i<4;i++){
                int nr = v.row + mv[i][0];
                int nc = v.col + mv[i][1];
                
                if(nr>4 || nr<0 || nc>4 || nc<0){
                    continue;
                }
                if(visited[nr][nc]==true){
                    continue;
                }
                if(place[nr].charAt(nc)=='X'){
                    continue;
                }
                //만약 위의 경우에 다 해당이 안되어, 이동을 한다면? 큐에 넣고 다시 bfs진행
                visited[nr][nc]=true;
                q.add(new Point(nr, nc, v.dist+1));
            }
        }
        //while문을 빠져나왔을 경우는 true를 반환해준다.
        return true;
    }
}