프로그래머스 코딩테스트 연습 - 거리두기 확인하기 (BFS)

# 주소

https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

# 문제

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

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

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

예를 들어,

위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다.	위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다.	위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를 지키지 않은 것입니다.
응시자가 앉아있는 자리(P)를 의미합니다.	빈 테이블(O)을 의미합니다.	파티션(X)을 의미합니다.

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

---

제한사항

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

---

입출력 예placesresult

[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

[1, 0, 1, 1, 1]

---

입출력 예 설명

입출력 예 #1

첫 번째 대기실

No.	0	1	2	3	4
0	P	O	O	O	P
1	O	X	X	O	X
2	O	P	X	P	X
3	O	O	X	O	X
4	P	O	X	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실

No.	0	1	2	3	4
0	P	O	O	P	X
1	O	X	P	X	P
2	P	X	X	X	O
3	O	X	X	X	O
4	O	O	O	P	P

• (0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.

세 번째 대기실

No.	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	O	X
3	O	X	X	O	P
4	P	X	P	O	X

• 모든 응시자가 거리두기를 지키고 있습니다.

네 번째 대기실

No.	0	1	2	3	4
0	O	O	O	X	X
1	X	O	O	O	X
2	O	O	O	X	X
3	O	X	O	O	X
4	O	O	O	O	O

• 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.

다섯 번째 대기실

No.	0	1	2	3	4
0	P	X	P	X	P
1	X	P	X	P	X
2	P	X	P	X	P
3	X	P	X	P	X
4	P	X	P	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

---

제한시간 안내

• 정확성 테스트 : 10초

※ 공지 - 2022년 4월 25일 테스트케이스가 추가되었습니다.

---

1. 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. ↩

# 문제 해설 및 코드 리뷰

import java.util.*;
class Node{
    int x;
    int y;
    int dir;
    Node(int x, int y, int dir){
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Solution {
    static int temp;
    static char[][] arr;
    static boolean[][] visit;
    static Queue<Node> queue;
    static int[][] d = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        for(int i = 0; i < places.length; i++){
            arr = new char[5][5];
            visit = new boolean[5][5];
            queue = new LinkedList<>();
            ArrayList<Node> list = new ArrayList<>();
            temp = 3;
            for(int j = 0; j < 5; j++){
                String temp = places[i][j];
                for(int k = 0; k < 5; k++){
                    arr[j][k] = temp.charAt(k);
                    if(arr[j][k] == 'P') {
                        list.add(new Node(j, k));
                    }
                }
            }
            if(list.size() == 0) {
                answer[i] = 1;
                continue;
            }
            for(int t = 0; t < list.size(); t++) {
                visit = new boolean[5][5];
                queue = new LinkedList<>();
                Node pp = list.get(t);
                int px = pp.x;
                int py = pp.y;
                queue.offer(new Node(px, py, 0));
                visit[px][py] = true;
                bfs(px, py);
                if(temp <= 2){
                    answer[i] = 0;
                    break;
                }
            }
            if(temp > 2)
                answer[i] = 1;
        }

        return answer;
    }
    static void bfs(int x, int y){
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            if(arr[now.x][now.y] == 'P' && (x != now.x || y != now.y)){
                temp = Math.min(temp, now.dir);
                break;
            }
            for(int i = 0; i < 4; i++){
                int nx = now.x + d[i][0];
                int ny = now.y + d[i][1];
                if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5)
                    continue;
                if(visit[nx][ny])
                    continue;
                if(arr[nx][ny] == 'X')
                    continue;
                queue.offer(new Node(nx, ny, now.dir + 1));
                visit[nx][ny] = true;
            }
        }
    }
}

진짜 ㅋㅋ 이거 해결했다면 30분 컷 했을텐데 4시간 정도 더 잡아먹었습니다.

bfs함수 안에서 

if(arr[now.x][now.y] == 'P' && (x != now.x || y != now.y)){

이 부분을 보시면 x와 y가 now.x 또는 now.y 중 하나만 달라도 되는데 둘 다 달라야 한다는 로직으로, ||대신에 &&을 쓰는 바람에 맞왜틀을 계속 시전하고 있었답니다.

반례 찾기에서 찾아봐도 진짜 아~~~~~~무리 봐도 걸릴게 없는데 똑같은 코드만 몇번을 봤는지 모르겠네요.

실제 시험에서 이랬을거라고 생각하니 생각만 해도 아찔합니다..

 

일주일만에 포스팅을 하는데 그동안 프로그래머스 lv 2짜리 문제를 좀 계속 푼다고 그랬습니다.

이미 포스팅한 내용들이 많아서 가급적이면 새롭거나 머리를 짜맸거나 기록을 하고 싶은 문제들 위주로 하려고 합니다.

내일이면 정규식을 활용한 문제도 풀이하여 올리겠습니다.

예전에 한 번 정규식 써서 푼 적이 있는데 그 때에는 다른분의 코드를 보고 아 정규식이구나 했지만 이번엔 문제 딱 보자마자 정규식이구나 해서 정규식 조건에 맞는 것들을 찾아서 구현했답니다 ㅎ.

어쨌든 각설하고 문제에서 무엇을 묻는지 먼저 정리해봅시다.

 

5 x 5크기의 String 배열이 주어지는데 각 배열 요소는 String 타입의 문자열입니다.

따라서 하나의 행만 하더라도 문자열이 5개가 되는 배열이 탄생하는데 이를 세로로 나열해봅시다.

그러고 난 뒤 각 문자열의 크기는 또 5이기 때문에 이것을 5 x 5 크기의 char타입의 배열에 담습니다.

따라서 최초에 주어지는 String [][]타입의 배열은 하나의 행에 대해 또 5 x 5의 배열이 탄생하는 것입니다.

그러므로 총 5 x 5의 배열이 5개 생기게 되는 것이지요.

이 배열로 무엇을 할거냐면, P가 들어와 있는 지점을 사람이 있는 곳이라 하고 X라 쳐져 있는 지점은 파티션이 가로 막고 있다고 설명합니다. O는 빈칸이기에 그냥 지나칠 수 있는 공간을 의미합니다.

그렇다고 할 때 사회적 거리두기를 위한 P끼리의 거리가 2칸 이하가 되면 거리두기를 지키고 있지 않기 때문에 0을, 모두가 3칸 이상이면 1을 담을 것이고 파티션이 막고 있다면 거리가 얼마든 신경쓰지 않고 탐색하지도 않습니다.

 

다른 분들의 생각을 살펴보면 대각선일 때에 탐색하시는 분도 계시던데 이 문제는 그냥 4방향으로만 탐색해도 충분히 풀 수 있답니다. 어렵게 생각하실 것 없어요. 왜그런지 봅시다.

static int temp;
static char[][] arr;
static boolean[][] visit;
static Queue<Node> queue;
static int[][] d = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

static 변수들은 다음과 같이 선언합니다.

또한

class Node{
    int x;
    int y;
    int dir;
    Node(int x, int y, int dir){
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}

Node 클래스를 오버라이딩 및 오버로딩하여 다형성을 지킵니다.

왜 파라미터를 2개 쓰는 클래스도 만들었는지는 나중에 다시 보겠습니다.

for(int i = 0; i < places.length; i++){
    arr = new char[5][5];
    visit = new boolean[5][5];
    queue = new LinkedList<>();
    ArrayList<Node> list = new ArrayList<>();
    temp = 3;
    for(int j = 0; j < 5; j++){
        String temp = places[i][j];
        for(int k = 0; k < 5; k++){
            arr[j][k] = temp.charAt(k);
            if(arr[j][k] == 'P') {
                list.add(new Node(j, k));
            }
        }
    }

arr와 visit과 queue를 for문이 돌 때마다 새로 생성합니다.

이는 for문이 돌 때마다 새로운 탐색을 해야하기 때문입니다.

그리고 Node 형식의 ArrayList를 list로 선언하는데 이 자료구조는 P를 담기 위함입니다.

정답을 비교할 temp는 3으로 초기화 해주시고 각각의 점이 P가 되면 모두 list에 담고 arr에는 각 점을 잘라서 넣습니다.

list크기가 0이면 볼 것도 없이 answer에 1 넣고 continue해주시고

for(int t = 0; t < list.size(); t++) {
    visit = new boolean[5][5];
    queue = new LinkedList<>();
    Node pp = list.get(t);
    int px = pp.x;
    int py = pp.y;
    queue.offer(new Node(px, py, 0));
    visit[px][py] = true;
    bfs(px, py);
    if(temp <= 2){
        answer[i] = 0;
        break;
    }
}

각 list 점에 대해 bfs문을 따로 실행할 것입니다.

왜냐하면 어떤 P점에서 출발하면 2보다 큰 지점이 다른 P점에서 출발했을 때 2보다 적을 수 있다고 해봅시다.

그럼 넓이 우선 탐색 기법의 특징인 동시에 탐색하는 BFS 특성상 queue에 모든 P점을 넣었다고 가정할 때 당연히 boolean타입의 visit도 처리를 해야할텐데, 그럼 경로가 서로 꼬이고 꼬여서 원하는 경로를 찾지 못할 것입니다.

제가 생각한 방법은 ArrayList에 모든 P점을 삽입한 뒤 그 점을 하나씩 꺼내면서 BFS문을 돌리는 것입니다.

따라서 for문이 돌 때마다 visit과 queue를 초기화해주고 점을 삽입하고 true처리하는 것입니다.

그럼 bfs문을 살펴봅시다.

static void bfs(int x, int y){
    while (!queue.isEmpty()) {
        Node now = queue.poll();
        if(arr[now.x][now.y] == 'P' && (x != now.x || y != now.y)){
            temp = Math.min(temp, now.dir);
            break;
        }
        for(int i = 0; i < 4; i++){
            int nx = now.x + d[i][0];
            int ny = now.y + d[i][1];
            if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5)
                continue;
            if(visit[nx][ny])
                continue;
            if(arr[nx][ny] == 'X')
                continue;
            queue.offer(new Node(nx, ny, now.dir + 1));
            visit[nx][ny] = true;
        }
    }
}

문제의 4시간 걸린 로직입니다.

if(arr[now.x][now.y] == 'P' && (x != now.x || y != now.y)){

arr점이 P점이 되면 저는 temp값과 거리값을 갱신하여 최솟값을 temp에 넣은 뒤 break하려고 했습니다.

그런데 최초에 점이 삽입될 때 이게 실행되면 곤란하기 때문에 x와 y가 now.x와 now.y가 달라야 한다고 짰습니다.

당연히 이게 맞을줄 알았습니다. 둘 다 동시에 달라야 한다 생각했으니까요.

근데 테스트 케이스는 맞는데 정답 제출하니 30%만 정답이고 나머지 다 틀렸더라고요.

가만.. 4시간 정도 다른 곳에서 원인을 찾다보니 하 설마 진짜 혹시? 해서 이 부분을 자세히 보니 이게 보이네요 ㅋㅋ.

&&라고 작성해버리면 x와 y가 둘 다 달라야 하기 때문에 바로 옆에 있는 'PP'이거나 위아래 붙어있는 PP들은 탐색을 하지 않게되겠지요. x 또는 y가 하나는 같으니까요 ㅋㅋ.......

에휴 그래서 여기서 시간 다 버렸습니다.

(CS 공부할랬는데 ㅠㅠ)

어쨌든 이 이후는 간단합니다.

for(int i = 0; i < 4; i++){
    int nx = now.x + d[i][0];
    int ny = now.y + d[i][1];
    if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5)
        continue;
    if(visit[nx][ny])
        continue;
    if(arr[nx][ny] == 'X')
        continue;
    queue.offer(new Node(nx, ny, now.dir + 1));
    visit[nx][ny] = true;
}

nx와 ny점을 새로 갱신해서 범위 벗어나거나 방문했거나 X지점은 모두 넘기고 외의 점만 queue에 삽입 후 방문 처리 해주심 됩니다.

이러면 왜 대각선은 고려하지 않아도 되는지 설명이 되시나요?

네..

대각선을 거친다는건 애초에 거리로만 따져도 2칸이기 때문에.. 상하좌우로 체크하나 대각선을 고려하나 똑같은 결과를 얻게됩니다.

오히려 코드만 길어지겠네요..

어쨌든 매우 간단한 문젠데 어렵게 풀어나가는거 보니 전 아직 많이 멀었네요.

감사합니다.