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

🖇️ 문제 링크

코딩테스트 연습 - 거리두기 확인하기

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

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

 

---

📝 문제 분석

BFS 탐색을 진행합니다. 거리가 3 이상이라면 더 이상 탐색하지 않아도 됩니다.

파티션으로 막혀 있을 경우 더 진행할 수 없으며, 자신이 아닌 응시자를 발견하면 FALSE를 리턴합니다.

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    int[] dy = {-1, 0, 1, 0}, dx= {0, 1, 0, -1};
    
    public int[] solution(String[][] places) {
       	int[] ans = new int[5];
        Arrays.fill(ans, 1);
        
        loop:
        for(int room = 0; room < 5; room++) {
            char[][] people = new char[5][5];
            for(int table = 0; table < 5; table++)
                people[table] = places[room][table].toCharArray();
        
            for(int i = 0; i < 5; i++) {
                for(int j = 0; j < 5; j++) {
                    if(people[i][j] == 'P') {
                        Queue<int[]> q = new LinkedList<>();
                        boolean[][] visit = new boolean[5][5];
                        q.add(new int[]{i, j});
                        visit[i][j] = true;
                        int distance = 0;
                        while(!q.isEmpty() && distance < 3) {
                            int s = q.size();
                            for(int c = 0; c < s; c++) {
                                int[] cur = q.poll();        
                                if(!(cur[0] == i && cur[1] == j) && people[cur[0]][cur[1]] == 'P') {
                                    ans[room] = 0;
                                    continue loop;
                                }

                                for(int d = 0; d < 4; d++) {
                                    int ny = cur[0] + dy[d];
                                    int nx = cur[1] + dx[d];

                                    if(ny < 0 || nx < 0 || ny >= 5 || nx >= 5 || visit[ny][nx] || people[ny][nx] == 'X')
                                        continue;
                                    visit[ny][nx] = true;
                                    q.add(new int[]{ny, nx});
                                }
                            }
                            distance++;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0