[Programmers] 거리두기 확인하기 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

문제 풀이

매개변수로 String[][] 형식으로 places가 주어지기 때문에 'P' 문자 하나를 찾아서 dfs로 길이 2만큼 탐색하여 거리두기가 가능한지 판별하였습니다.

우선, 4방향 탐색보단 좌, 우 ,하 3방향만 탐색해도 충분히 전체를 확인할 수 있어 3방향으로 검사하고 visited를 활용하여 중복된 칸은 확인하지 않았습니다.

dfs탐색 중, 다른 'P'를 만나면 불가능한 경우이기 때문에 전역변수로 설정한 possible을 0으로 설정 후 return하여 answer 배열에 넣어주었습니다. 0인 경우엔 더 이상 탐색이 필요없어 break로 빠져나왔습니다.

코드

import java.util.*;

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[PLACE_NUM];
        Arrays.fill(answer, 1);
        
        for(int i=0; i<PLACE_NUM; i++) {
            loop: for(int j=0; j<PLACE_NUM; j++) {
                for(int k=0; k<PLACE_NUM; k++) {
                    if(places[i][j].charAt(k) == 'P') {
                        possible = 1;
                        dfs(places, 0, i, j, k, new boolean[PLACE_NUM][PLACE_NUM]);
                        answer[i] = possible;
                        if(possible ==0) break loop;                        
                    }
                }
            }
        }
        
        return answer;
    }
    
    int[] dx = {0, 1, 0};
    int[] dy = {1, 0, -1};
    int DIR_NUM = 3;
    int PLACE_NUM = 5;
    int possible = 1;
    public void dfs(String[][] places, int depth, int i, int x, int y, boolean[][] visited) {        
        if(depth == 2) {
            return;
        }
        
        visited[x][y] = true;        
        for(int dir=0; dir<DIR_NUM; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            if(!isRange(nx, ny) || places[i][nx].charAt(ny) == 'X' || visited[nx][ny]) continue;
            if(places[i][nx].charAt(ny) == 'P') {
                possible = 0;
                return;
            }
            dfs(places, depth+1, i, nx, ny, visited);
        }        
    }
    
    public boolean isRange(int x, int y) {
        return x>=0 && y>=0 && x<PLACE_NUM && y<PLACE_NUM;  
    }
    
}