프로그래머스 거리두기 확인하기(JAVA)

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

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

 

저는 해당 문제를 DFS를 이용해 문제를 해결하였습니다.

각각의 P에서 DFS를 이용해 깊이가 2까지 들어가기 전에 P가 있는지를 확인하였습니다.

저는 dir(이전 방향)를 통해 이전 방향으로 가지 않게 구현하였습니다.

또한, dir이 -1이면 처음들어온 것으로 간주하여 이때는 현재 값이  P인지를 확인하지 않습니다.

 

import java.util.*;
class Solution {
    private static final int SIZE = 5;
    private static final int[] dy = {-1,0,1,0};
    private static final int[] dx = {0,-1,0,1};
    private static final int DEPTH_LIMIT = 2;
    private static int cal(String[]place){
        char[][] arr = new char[SIZE][];
        for(int i = 0 ; i < 5 ; i++){
            arr[i] = place[i].toCharArray();
        }
        for(int i = 0 ; i < SIZE ; i++){
            for(int j = 0 ; j < SIZE ; j++){
                if(arr[i][j] == 'P' && !checkRule(0,i,j,-1,arr)){
                    return 0;
                }
            }
        }
        return 1;
    }
    private static boolean checkRule(int depth , int y,int x,int dir,char[][] arr){
        if(dir != -1 && arr[y][x] == 'P'){
            return false;
        }
        if(depth == DEPTH_LIMIT){
            return true;
        }
        if(dir != -1){
            dir += 2;
            dir %= 4;
        }
        for(int i = 0 ; i < 4 ; i++){
            if(dir == i){
                continue;
            }
            int ny = y + dy[i];
            int nx = x + dx[i];
            if( ny >= 0 && ny < SIZE && nx >= 0 && nx < SIZE 
                && arr[ny][nx] != 'X' && !checkRule(depth+1,ny,nx,i,arr)){
                return false;
            }
        }
        return true;
    }
    public int[] solution(String[][] places) {
        int pLength = places.length;
        int[] answer = new int[pLength];
        for(int i = 0 ; i < pLength ; i++){
            answer[i] = cal(places[i]);
        }
        return answer;
    }
}