[프로그래머스] 거리두기 확인하기(2021 카카오 채용연계형 인턴십)-JAVA

[문제 설명]

아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

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을 담습니다.

[풀이]

해당 문제의 핵심은 BFS/DFS를 약간 응용할 수 있는지 물어보는 것 같습니다. 이중 for문을 통해 배열에서 P의 위치를 찾고 그 위치를 기반으로 주변 2칸 내에 다른 P가 있는지 물어보는 문제로, 저는 BFS를 통해 풀었습니다. 초기 P의 위치에서 1칸 이동할때 마다 이동 횟수를 더하는 number 변수에 1을 더해주었고 총 이동 횟수가 2를 넘으면 해당 BFS를 종료시킬 수 있도록 설정하였습니다. 

 

다음은 최종 코드입니다. 

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    static char[][] map;
    static int[] d1 = {1, -1, 0, 0};
    static int[] d2 = {0, 0, 1, -1};
    static int[] result = {1,1,1,1,1};
    static boolean[][] visit;
    public int[] solution(String[][] places) {
        int num=0;
        for (int k = 0; k < 5; k++) {
            map = new char[5][5];
            for (int i = 0; i < 5; i++) {
                map[i] = places[num][i].toCharArray();
            }
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (map[i][j] == 'P') {
                        visit = new boolean[5][5];
                        int inx=BFS(new Got(i, j, 0));
                        if(inx==0) {
                            result[num]=0;
                            break;
                        }
                    }
                }
                if(result[num]==0) break;
            }
            num++;
        }
        return result;
    }

    private static int BFS(Got got) {
        visit[got.x][got.y]=true;
        Queue<Got> q = new LinkedList<>();
        q.add(got);
        int ans = 1;
        
        while (!q.isEmpty()) {
            if(ans==0)break;
            Got gos = q.poll();
            if(gos.number<2){
                for (int i = 0; i < 4; i++) {
                    int xx = gos.x + d1[i];
                    int yy = gos.y + d2[i];
                    if(xx>=0&&yy>=0&&xx<5&&yy<5&&map[xx][yy]!='X'&&visit[xx][yy]==false){
                        if(map[xx][yy]=='P'){
                            ans=0;
                            break;
                        }else q.add(new Got(xx,yy, gos.number+1));

                    }
                }
            }

        }
        return ans;
    }
}

class Got{
    int x;
    int y;
    int number;

    public Got(int x, int y, int number) {
        this.x = x;
        this.y = y;
        this.number = number;
    }
}