2021 카카오 인턴십 - 거리두기 확인하기

문제 설명

제한사항

문제 해석

해당 문제는 탐색 문제입니다. 문제에서 주어진 제한사항에 따르면 대기실은 항상 5개라고 친절히 알려줍니다.

BFS, DFS 둘 다 풀이가 가능하지만 BFS가 조금 더 정답에 가까운 알고리즘인 것 같습니다.

"벽"이라는 개념만 체크하면 쉽게 풀 수 있습니다.

풀이

최초에는 "벽" 개념을 망각하고 풀이를 시작해서 코드가 다소 복잡해졌습니다..

풀이는 단순합니다.

각 대기실의 모든 응시자 P마다 거리가 2인 지점들을 모두 탐색하고 맨해튼 거리가 2 이상인 응시자가 있다면 바로 0을 반환해줍니다.

코드

import java.util.*;

class Solution {
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};
    
    static class Node {
        public int x, y, dist;
        Node(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    
    public int[] solution(String[][] places) {
        char[][] mat;
        Queue<Node> que;
        Queue<Node> pos;
        int[] answer = new int[places.length];
        
        for(int i=0 ; i<places.length ; ++i) {
            que = new LinkedList<Node>();
            pos = new LinkedList<Node>();
            mat = new char[5][5];
            for(int j=0 ; j<5 ; ++j) {
                mat[j] = places[i][j].toCharArray();
                for(int k=0 ; k<5 ; ++k) {
                    if(mat[j][k] == 'P') {
                        pos.add(new Node(j, k, 0));
                    }
                }
            }
            int ans=1;
            while(!pos.isEmpty()) {
                boolean[][] visit = new boolean[5][5];
                que.add(pos.poll());
                if(BFS(mat, que, visit) == 0) {
                    ans = 0;
                    break;
                }
            }
            answer[i] = ans;
        }
        
        return answer;
    }
    
    public static int BFS(char[][] mat, Queue<Node> que, boolean[][] visit) {
        while(!que.isEmpty()) {
            Node node = que.poll();
            int x = node.x;
            int y = node.y;
            int dist = node.dist;
                  
            if(x < 0 || y < 0 || x >= 5 || y >= 5
              || dist == 3) {
                continue;
            }
            else if(visit[x][y]) {
                continue;
            }
            visit[x][y] = true;
            
            if(dist > 0) {
                switch(mat[x][y]) {
                    case 'P':
                        return 0;
                    case 'X':
                        continue;
                }
            }
            
            for(int i=0 ; i<4 ; ++i) {
                que.add(new Node(x+dr[i], y+dc[i], dist+1));
            }
        }
        
        return 1;
    }
}