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

2021 카카오 채용연계형 인턴십 > 거리두기 확인하기 문제를 풀어보았다.

간단한 dfs 문제로 depth 처리를 깔끔하게 해주면 해결되는 문제였다.

5x5 고정 배열 5개 주어지기에 웬만하면 시간초과나 메모리 초과 오류가 나지 않는다.

그렇기에 dfs를 선택했고,

사용자 기준으로 상하좌우를 탐색하는데, O를 만난다면 한번 더 탐색해주면 된다.
이에 따른 처리를 depth를 통해 판단했다.

그림처럼 (0,0) 에서 탐색해 (1,0)의 O를 만난다면 추가적으로 탐색이 필요하다.
그래서 (2,0)의 방문하지 않은 P를 만나면 거리두기가 지켜지지 않은 것이다.

종료 조건은

• depth가 3을 초과한다면(첫 번째 O를 만났을 때만 추가 탐색해야 하기에)
• X를 만난다면
• 방문하지 않은 P를 만난다면 (이는 거리두기를 지키지 않은 경우)

이다.

거리두기를 지키지 않은 경우가 하나만 존재하더라도, 그 경우는 실패가 되기에 check 변수를 통해 가지치기를 해주었다.

/*
5x5 고정 배열 5개 주어짐.
P(사용자) 기준으로 상하좌우 탐색. O를 만난다면 한번더 탐색, X를 만난다면 중단
탐색 중 시작 P가 아닌 P를 만나게 된다면 거리두기를 지키지 않는 것으로 판단
*/


class Solution {
    public static boolean[][] visited;
    public static int check;
    
    public int[] solution(String[][] places) {
        int[] result = new int[5];
        
        for (int i=0; i<5; i++) {
            visited = new boolean[5][5];
            check = 1;
            for (int j=0; j<5; j++) {
                for (int k=0; k<5; k++) {
                    if (check == 0) continue;
                    
                    if (places[i][j].charAt(k) == 'P') {
                        visited[j][k] = true;
                        dfs(places, i, j, k, 0);
                    }
                }
            }
            result[i] = check;
        }
        
        return result;
    }
    
    public void dfs(String[][] places, int i, int j, int k, int depth) {
        if (j < 0 || k < 0 || j >= 5 || k >= 5) {
            return;
        }
        
        if (places[i][j].charAt(k) == 'X' || depth >= 3) {
            return;
        }
        
        if (!visited[j][k] && places[i][j].charAt(k) == 'P') {
            check = 0;
            return;
        }
        
        dfs(places, i, j+1, k, depth+1);
        dfs(places, i, j, k+1, depth+1);
        dfs(places, i, j-1, k, depth+1);
        dfs(places, i, j, k-1, depth+1);
    }
}