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

문제

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

프로그래머스

 

 

풀이 과정

위쪽 방향은 이미 다 탐색했으므로 또 확인할 필요 없이 3방향 탐색하면서, (거리가 2 초과)거나 (범위)를 벗어나거나 (파티션이 있을 경우) 더이상 탐색을 하지 않고 종료한다.

이때, 거리가 2이하인데, 'P'가 있는 경우 답은 0으로 체크하고 더 이상 탐색하지 않는다.

+) 처음엔 DFS를 떠올렸는데, 구체적인 해결 방안을 생각해내는 데 시간이 걸렸다.. 알고리즘은 꾸준히 푸는 것이 중요한 것 같다.

import java.util.*;

class Solution {
    
    int[] answer;
    int[] dx = {0, 1, 0}, dy = {1, 0, -1};
    boolean[][] visited;
    
    public int[] solution(String[][] places) {
        answer = new int[5];
        visited = new boolean[5][5];
        
        Arrays.fill(answer, 1);

        for(int i=0; i<5; i++){
            outloop : for(int j=0; j<5; j++){
                for(int k=0; k<5; k++){
                    if(places[i][j].charAt(k)=='P'){
                        visited[j][k] = true;
                        dfs(i, j, k, 0, places[i]);
                        visited[j][k] = false;
                    }
                    if(answer[i] == 0) break outloop;
                }
            }   
        }
        
        return answer;
    }
    
    public void dfs(int no, int x, int y, int count, String[] place){
        if(count > 2) return;
        if(count > 0 && place[x].charAt(y) == 'P'){
            answer[no] = 0;
            return;
        }
        
        for(int i=0; i<3; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=5 || ny<0 || ny>=5 || visited[nx][ny] || place[nx].charAt(ny) == 'X') continue;
            visited[nx][ny] = true;
            dfs(no, nx, ny, count+1, place);
            visited[nx][ny] = false;
            
        }
        
    }
    
}