[프로그래머스] 거리두기 확인하기 (Java)

문제

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

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

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

 

풀이

BFS알고리즘으로 풀었다. 

맵을 순회하면서, 값이 P일 경우 해당 좌표로 BFS를 시작하여 depth 2까지만 탐색하여 

해당 범위 내 P가 있을 경우 0을 리턴한다. 

 

소스코드

import java.util.*;
class Solution {        
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];        
        for(int i = 0; i < places.length; i++){
            char[][] map = new char[5][5];
            for(int j = 0; j < 5; j++){
                map[j] = places[i][j].toCharArray(); 
            }
            answer[i] = process(map);
        }        
        
        return answer;
    }
    
    public int process(char[][] map){
        // 잘 지켜지고 있으면 1, 지키지 않았으면 0
        for(int i = 0; i < 5; i ++){
            for(int j = 0; j < 5; j++){
                if(map[i][j] == 'P' && bfs(map, i, j) == 0) return 0;
            }
        }
        return 1;
    }
    
    public int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    public int bfs(char[][] map, int sX, int sY) {
        boolean[][] visited = new boolean[5][5];
        
        Queue<Integer> que = new LinkedList<Integer>();
        visited[sX][sY] = true;
        que.offer(sX);
        que.offer(sY);
        que.offer(0);
        
        while(!que.isEmpty()){
            int x = que.poll();
            int y = que.poll();
            int cnt = que.poll();
            
            for(int[] d : dir){
                int nx = x + d[0];
                int ny = y + d[1];
                int nCnt = cnt + 1;
                if(isValid(visited, map, nx, ny, nCnt)){
                    if(map[nx][ny] == 'P') return 0;
                    visited[nx][ny] = true;
                    que.offer(nx);
                    que.offer(ny);
                    que.offer(nCnt);
                }
            }
        }
        
        return 1;
    }
    
    public boolean isValid(boolean[][] visited, char[][] map, int x, int y, int cnt){
        if(x < 0 || y < 0 || x >= 5 || y >= 5) return false;
        if(visited[x][y] || map[x][y] == 'X' || cnt == 3) return false;
        return true;
    }
}