프로그래머스 거리두기 확인하기 자바

문제는 다음과 같다.
https://school.programmers.co.kr/learn/courses/30/lessons/81302#fn1

풀이는 다음과 같다.

class Solution {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static boolean[][] visited;
    static boolean a;
    static char[][] room;
    
    public int[] solution(String[][] places) {
        int[] answer = {1, 1, 1, 1, 1};
        
        for(int i = 0 ; i < 5 ; i++) {
            room = new char[5][5];
            a = false;
            
            for(int j = 0 ; j < 5 ; j++) {
                room[j] = places[i][j].toCharArray();
            }
            
            for(int r = 0 ; r < 5 ; r++) {
                for(int c = 0 ; c < 5 ; c++) {
                    if(room[r][c] == 'P') {
                        visited = new boolean[5][5];
                        visited[r][c] = true;
                        backTracking(0, r, c);
                    }
                    
                    if(a) {
                        answer[i] = 0;
                        break;
                    }
                }
                if(a) break;
            }
        }
        
        return answer;
    }
    
    static void backTracking(int depth, int r, int c) {
        if(depth == 2) return;
        
        for(int i = 0 ; i < 4 ; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue; //index검사
            if(visited[nr][nc]) continue; //방문검사
            if(room[nr][nc] == 'X') continue; //못갈곳 검사
            
            if(room[nr][nc] == 'P') { //거리두기 못지킨경우
                a = true;
                return;
            }
            
            visited[nr][nc] = true;
            backTracking(depth+1, nr, nc);
        }
    }
}

풀이에 대한 설명으로,
사람P 이 있는 위치를 골라서
해당 위치로 맨해튼 거리 2 이내의 점들을 탐색하고,

만약 맨해튼 거리 2 이내의 점들에서
또다른 사람P이 있다면, 거리두기 실패 (false)
없다면, 거리두기 성공 (true) 를 통해

int[] answer에 값을 넣어주는 로직이다.

유의해야 할 점은
초깃값 설정이 약간 헷갈리고, (String[][]에서 char[][]를 여러개 만들어야 함)

백트래킹 로직에서 보아야 할 내용은 아래와 같다.

for(int i = 0 ; i < 4 ; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue; //index검사
            if(visited[nr][nc]) continue; //방문검사
            if(room[nr][nc] == 'X') continue; //못갈곳 검사
            
            if(room[nr][nc] == 'P') { //거리두기 못지킨경우
                a = true;
                return;
            }
            
            visited[nr][nc] = true;
            backTracking(depth+1, nr, nc);
        }

깊이가 1일때 2일때 해당 깊이에 도달해서 검증하는게 아니라,

예를 들어
if(depth == 1 || depth == 2) 일때 
주어진 매개변수 r, c 를 통해 검사하는게 아니라

내가 앞으로 도달할 점을 검사해서

//지금의 점이 아닌 도달할 점 nr, nc 검사
if(room[nr][nc] == 'P') { //거리두기 못지킨경우
                a = true;
                return;
            }

탈출 로직을 쉽게 해준다.

if(depth == 2) return;