자바(JAVA) - 거리두기 확인하기(Programmers : 81302)

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

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

다 됐다 싶었으니, 몇몇 실패 케이스 때문에 시간이조금 소요됐다. (디버깅이 상당히 어려웠다..)

나중에 보니 bfs 로 해결한 분들이 많던데, 나는 그냥 익숙하면서 아직 많이 부족한  dfs로 정답을 구했다.

각 P의 위치를 시작으로 dfs를 실행, 거리두기 조건에 충족하지 않을 경우 stopper 변수를 업데이트하고, 재귀 호출을 중단하는 식으로 정답을 구했다.

다 풀고 아쉬웠던 부분은 문제에서 주어진 내용들을 좀 더 활용했으면 더 좋았으련만,, 급한 마음에 너무 결과값에만 집착했다.

다음엔 더 꼼꼼히 읽고, 더 이해하기 쉬운 코드를 만들 수 있도록 노력, 또 노력해야겠다. 

 

class Solution {
    String[][] places;
    int[] answer;
    boolean goodToSit = true;
    int len = 0;
    boolean[][] visited;

    public int[] solution(String[][] places) {
        len = places.length;
        int[] answer = new int[len];
        visited = new boolean[len][len];
        for (int i = 0; i < places.length; i++) {
            // System.out.println("===============>  "+ i);
            for (int j = 0; j < places[i].length; j++) {
                if (!goodToSit) break;
                for (int k = 0; k < places[i][j].length(); k++) {
                    char currChar = places[i][j].charAt(k);
                    if (!goodToSit) break;

                    if (currChar == 'P') {
                        // System.out.println("   UPDATED P Location >  "+ j + " / " + k);
                        dfs(places[i], j, k, 0);
                        visited = new boolean[len][len];
                    }
                }
            }
            answer[i] = goodToSit ? 1 : 0;
            goodToSit = true;
        }
        
        return answer;
    }


    public void dfs(String[] places, int r, int c, int distance) {
        // System.out.println(r + " / " + c + " / " + distance);
        if (!goodToSit) {
            return;
        }

        if (r == len|| c == len || r < 0 || c < 0 || visited[r][c] || places[r].charAt(c) == 'X') {
            // System.out.println("WRONG POSITION");
            return;
        }

        if (distance != 0 && distance <= 2 && places[r].charAt(c) == 'P') {
            // System.out.println("GoodToSit to FALSE");
            goodToSit = false;
            return;
        }

        if (!visited[r][c]) {
            visited[r][c] = true;
            dfs(places, r + 1, c, distance + 1);
            dfs(places, r - 1, c, distance + 1);
            dfs(places, r, c + 1, distance + 1);
            dfs(places, r, c - 1, distance + 1);
            visited[r][c] = false;
        }
    }
}