[Programmers] 2021 카카오 채용연계형 인턴십 : 거리두기 확인하기 JAVA

 

💬 문제 설명

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

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

예를 들어,

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

 

🔨 입출력 예

1. 입출력 예

첫 번째 대기실

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

두 번째 대기실

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

세 번째 대기실

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

네 번째 대기실

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

다섯 번째 대기실

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

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

 

💻 Solution.java

• 좌표 정보와 거리 정보를 저장할 클래스 Point를 생성한다
• isKeepDistance() 함수로 한 대기실씩 거리두기가 제대로 되고 있는지 확인한다.
  • 응시자의 위치를 찾아 bfs를 시작한다.
• 거리두기를 확인하기 위해서 bfs 알고리즘을 사용했다.
  • 응시자 위치를 시작으로 좌표를 저장한다
  • 맨해튼 거리를 계산하기 위해서 다음으로 갈 좌표는 십자로만 움직이고, 거리를 point.dist에 저장한다
    • 응시자와 떨어진 거리(point.dist + 1)가 2보다 커지게 되면 bfs를 중지한다
    • 파티션을 접하면 스킵
    • 맨해튼 거리 2이하에 다른 응시자를 만나면 bfs 중지, 0리턴

import java.util.*;

class Point{
    int x;
    int y;
    int dist;
    
    Point(int x, int y, int dist){
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}

class Solution {
    static int[] dy = {-1,0,1,0};
    static int[] dx = {0,1,0,-1};
    
    public int bfs(int x, int y, String[] place){
        boolean[][] visited = new boolean[5][5];
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, 0));  // 응시자 위치를 시작점으로 지정
                    
        while(!q.isEmpty()){
            Point cur = q.poll();
            visited[x][y] = true;
            for(int k = 0; k < 4; k++){
                int ny = cur.y + dy[k];
                int nx = cur.x + dx[k];

                // 응시자의 다음 거리가 2보다 클 경우 정지 
                if(cur.dist + 1 > 2)
                    break;

                // 대기실의 범위 검사와 중복 검사
                if(nx < 5 && ny < 5 && nx >= 0 && ny >= 0 && !visited[nx][ny]){
                    // 파티션일 있는 경우 거리를 재지 않는다
                    if(place[nx].charAt(ny) == 'X')
                        continue;
                    // 거리두기가 이뤄지지 않으면 '0'리턴
                    else if(place[nx].charAt(ny) == 'P')
                        return 0;
                    // 빈 테이블의 경우 거리를 재준다
                    else
                        q.add(new Point(nx, ny, cur.dist + 1));
                }
            }
        }
        
        return 1;
    }
    
    public int isKeepDistance(String[] place){
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                // 응시자를 중심으로 bfs 시작
                if(place[i].charAt(j) == 'P'){ 
                    // 거리두기를 지키지 않고 있으면 0 리턴
                    if(bfs(i, j, place) == 0){
                        return 0;
                    }
                }                
            }
        }

        // 모두 거리두기를 하고 있으면 1 리턴
        return 1;
    }
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        for(int i = 0; i < 5; i++){
            answer[i] = isKeepDistance(places[i]);
        }
        
        return answer;
    }
}