[JAVA] 프로그래머스: 거리두기 확인하기 | Queue와 LinkedList | BFS 풀이 방법

---

2021 KAKAO 채용연계형 인턴십 거리두기 확인하기

프로그래머스

 

🔒 문제 설명

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야 하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리 두기를 위하여 응시자들끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

 

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리 두기를 잘 지키고 있는지 알고 싶어 졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리 두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

---

🔎 1차 풀이:

내가 이 문제를 처음 풀었을 때는 거리 두기에 실패하는 경우를 총 세 가지로 나누고,

1. crossOne: 십자가 방향으로 ds=1인 영역에서 P가 발견되는 경우 
2. crossTwo: 십자가 방향으로 ds=2인 영역에서 P가 발견되는 경우 
3. diagonal: 기준 P와 꼭짓점이 맞닿은 대각선 방향 영역에서 P가 발견되는 경우 
      > 두 P 영역과 변이 맞닿아 있는 영역이 하나라도 'O'면 false

 

각 경우에 따른 좌표를 아래와 같이 지정해 P가 발견될 때마다 해당 P를 기준으로 세 경우를 확인하는 방법으로 코드를 구성했다.

    static int [][] crossOne = {{0,1}, {1,0}, {-1,0}, {0,-1}};
    static int [][] crossTwo = {{0,2}, {2,0}, {-2,0}, {0,-2}};
    static int [][] diagonal = {{-1,-1}, {1,1}, {-1,1}, {1,-1}};

 

그림으로 자세히 살펴보자면

[1] crossOne: 십자가 방향으로 ds=1인 영역에서 P가 발견되는 경우 false

---

[2] crossTwo: 십자가 방향으로 ds=2인 영역에서 P가 발견되는 경우 false

---

[3] diagonal: 기준 P와 꼭짓점이 맞닿은 대각선 방향 영역에서 P가 발견되는 경우 

      > 두 P 영역과 변이 맞닿아 있는 영역이 하나라도 'O'면 false

그림에서 빨간색 P는 현재 기준인 노란색 P와 사이에 가림막이 아닌 빈테이블(O)이 있으므로 거리 두기에 실패했다.

반면 아래 파란색 P는 노란색 P와 가림막으로 완전히 분리되어 있으므로 거리 두기에 성공한 경우이다.

 

이를 코드로 구현하면 아래와 같다.

 

 

🗝️ 1차 해결 코드

class Solution {

    static String[][] waitingRoom;
    static int[][] crossOne = {{0,1},{1,0},{-1,0},{0,-1}};
    static int[][] crossTwo = {{0,2},{2,0},{-2,0},{0,-2}};
    static int[][] diagonal = {{-1,-1},{1,1},{-1,1},{1,-1}};

    public int[] solution(String[][] places) {

        int[] answer = new int[5];

        for( int i = 0; i < 5; i++ ){
            waitingRoom = new String[5][5];
            for( int j = 0; j < 5; j++){
                String[] line = places[i][j].split("");
                for( int k = 0; k < 5; k++ ){
                    waitingRoom[j][k] = line[k];
                }
            }
            answer[i] = checkDistance(waitingRoom);
        }

        return answer;
    }

    public static int checkDistance( String[][] waitingRoom ){

        for( int i = 0; i < 5; i++ ){
            for( int j = 0; j < 5; j++ ){
                if( waitingRoom[i][j].equals("P")){
                    //[1] 십자가 방향으로 +-1 주위의 유저 체크
                    int[][] crossOneCheck = crossOne;

                    for( int[] coordinate: crossOneCheck ){
                        int x = coordinate[0] + i;
                        int y = coordinate[1] + j;

                        if( x < 0 || y < 0 || x > 4 || y > 4 ) continue;

                        // 십자가 방향 유저 한 명이라도 있으면 0 리턴
                        if(waitingRoom[x][y].equals("P")) return 0;

                    }

                    // [2] 십자가 방향으로 +- 2
                    int[][] crossTwoCheck = crossTwo;

                    for( int[] coordinate: crossTwoCheck ){
                        int x = coordinate[0] + i;
                        int y = coordinate[1] + j;

                        if( x < 0 || y < 0 || x > 4 || y > 4 ) continue;

                        // 십자가 방향 유저 있으면 사이에 가림막 없을 경우 0 리턴
                        if(waitingRoom[x][y].equals("P")){
                            if(x == i) {
                                if (!waitingRoom[x][(j + y) / 2].equals("X")) return 0;
                            }
                            else if(!waitingRoom[(i+x)/2][y].equals("X")) return 0;
                        }

                    }
                    
                    // [3] 대각선 방향으로 존재하는지 확인
                    int[][] diagonalCheck = diagonal;

                    for( int[] coordinate: diagonalCheck ){
                        int x = coordinate[0] + i;
                        int y = coordinate[1] + j;

                        if( x < 0 || y < 0 || x > 4 || y > 4 ) continue;

                        // 십자가 방향 유저 있으면 사이에 가림막 없을 경우 0 리턴
                        if(waitingRoom[x][y].equals("P")){
                            if(!waitingRoom[x][j].equals("X") | !waitingRoom[i][y].equals("X")) return 0;
                        }
                    }
                }
            }
        }
        return 1;
    }
}

---

 

그런데 세 가지로 나눈 경우에 중복된 경우가 존재하고, 훨씬 단순화할 수 있는 방법을 알아냈다. 

알고리즘은 bfs를 사용해서 자료구조 큐와 LinkedList를 사용하면 간단하고 빠르게 구현할 수 있다.

 

로직은 for문을 순회하며 places 배열을 돌다가 P가 나오면 bfs매서드를 호출한다.

bfs매서드는 사방탐색을 진행할 큐 searchQueue를 갖고, 해당 큐에 있는 요소들에 대해 사방탐색을 진행한다.

 

예를 들면 다음과 같다.

먼저 맨 처음 bfs에 들어오면 현재 기준이 되는 P 좌표값을 큐에 offer(삽입)한다.

현재 발견된 P를 기준으로 위아래, 양 옆 영역을 탐색한다.

 

---

만약 사방탐색을 하다가 이웃한 P를 발견하면 -> 바로 false 리턴

혹은 빈테이블 O를 발견하면 -> 해당 O를 다음 사방탐색 대상 큐에 삽입한다

---

그리고 이번엔 해당 O에 대해 사방탐색을 진행하는데 이때도 마찬가지 주위에 P를 찾으면 된다.

여기서 만약 P를 찾는다면, 두 가지 경우를 따져봐야 한다.

1. 이미 확인한 기존 P(노란색)가 아닌지, 
2. 기존 P(노란색)와의 맨해튼거리가 2 이하인지 

-> 위 두 가지 경우에 모두 해당한다면 노란색 P와 거리 두기를 하고 있지 않으므로 false를 리턴한다.

 

위 로직을 코드로 구현하면 아래와 같다. 

 

🗝️ 2차 해결 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[] solution(String[][] places) {

        int[] answer = new int[5];

        for( int i = 0; i < 5; i++ ){
            boolean check = true;
            String[] waitingRoom = places[i];
            for( int r = 0; r < 5; r++ ){
                for( int c = 0; c < 5; c++ ){
                    if(waitingRoom[r].charAt(c)=='P'){
                        if(!bfs(r,c,waitingRoom)){
                            check = false;
                            break;
                        }
                    }
                }
                if(!check) break;
            }
            answer[i] = check ? 1 : 0;
        }
        return answer;
    }

    public boolean bfs( int or, int oc, String[] waitingRoom ){
        // or: original row, oc: original column
        System.out.println("bfs");

        int[] x = { 0, 1, 0, -1 };
        int[] y = { 1, 0, -1, 0 };

        Queue<int[]> searchQueue = new LinkedList<>();
        searchQueue.offer(new int[]{or, oc});

        while(!searchQueue.isEmpty()){
            int[] search = searchQueue.poll();

            for(int i = 0 ; i < 4; i++ ){
                int r = search[0] + x[i];
                int c = search[1] + y[i];

                int bc = Math.abs(or-r) + Math.abs(oc-c);

                if( r<0 || c<0 || r>4 || c>4 || ( r==or && c==oc )) continue;

                if( waitingRoom[r].charAt(c)=='P' && bc <= 2 ) {
                    return false;
                }

                if( waitingRoom[r].charAt(c)=='O' && bc < 2 ) {
                    searchQueue.offer( new int[]{r,c} );
                }
            }
        }

        return true;
    }
}