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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/81302#

이 문제는 bfs를 이용하여 풀 수 있습니다. 문제의 제한 조건이 5X5 행렬 내에서 거리 2 이하만 체크하면 되므로 모든 P에 대해서 bfs를 돌려 칸막이가 있는 경우 이동하지 못하는 조건을 추가하여 진행하면 쉽게 풀 수 있습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static int[] dy = {1,0,-1,0};
    static int[] dx = {0,1,0,-1};
    static int[][] map = new int[5][5];
    static int bfs(Pair req){
        boolean[][] check = new boolean[5][5];
        check[req.y][req.x] = true;
        Queue<Pair> queue = new LinkedList<>();
        queue.add(req);
        
        while(!queue.isEmpty()){
            Pair curr = queue.poll();
            
            if(curr.cnt>2) continue;
            if(map[curr.y][curr.x]==2 && curr.cnt!=0){
                return 0;
            }
            
            for(int i=0;i<4;i++){
                int ny = curr.y + dy[i];
                int nx = curr.x + dx[i];
                if(ny<0 || ny>=5 || nx<0 || nx>=5) continue;
                
                if(!check[ny][nx] && map[ny][nx]!=1){
                    check[ny][nx] = true;
                    queue.add(new Pair(ny,nx,curr.cnt+1));
                }
            }
        }
        
        return 1;
    }
    
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];

        for(int i=0;i<places.length;i++){
            ArrayList<Pair> start = new ArrayList<>();
            map = new int[5][5];
            
            // 대기실 정보 초기화
            for(int j=0;j<places[i].length;j++){
                String str = places[i][j];
                
                for(int k=0;k<str.length();k++){
                    if(str.charAt(k)=='P'){
                        start.add(new Pair(j,k,0));
                        map[j][k] = 2;
                    }
                    else if(str.charAt(k)=='X') map[j][k] = 1;
                }
            }
            
            // P의 위치에서 거리 2까지 체크
            int res = 1;
            for(int j=0;j<start.size();j++){
                Pair curr = start.get(j);
                if(bfs(curr)==0){
                    res=0;
                    break;
                }
            }
            answer[i]=res;
        }
        
        return answer;
    }
}

class Pair{
    int y,x,cnt;
    
    Pair(int y, int x, int cnt){
        this.y = y;
        this.x = x;
        this.cnt = cnt;
    }
}