[프로그래머스 / Level4] 동굴 탐험 (Java)

순서에 상관 없이 방문 가능 여부만 판단하면 되는 문제도 있다.

문제 보기

사용한 것

• 그래프를 탐색하기 위한 BFS
• 선후관계를 저장하기 위한 int 배열 before, after

풀이 방법

• BFS를 수행하며 다음 노드에 대해 visited를 2로 설정한다.
• 다음 노드지만 선후관계가 충족이 되지 않은 경우 visited를 1로 설정한다.
• 현재 방문 노드가 선후관계의 선 노드라면, 후 노드가 방문 가능했던 경우에만 방문한다.

코드

class Solution {

    private int size;
    private List<List<Integer>> graph;
    private int[] before;
    private int[] after;

    public boolean solution(int n, int[][] path, int[][] order) {
        init(n, path, order);
        return canSearchAllRooms();
    }

    private void init(int n, int[][] path, int[][] order) {
        size = n;
        graph = new ArrayList<>();
        before = new int[n];
        after = new int[n];
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] arr : path) {
            graph.get(arr[0]).add(arr[1]);
            graph.get(arr[1]).add(arr[0]);
        }
        for (int[] arr : order) {
            before[arr[1]] = arr[0];
            after[arr[0]] = arr[1];
        }
    }

    private boolean canSearchAllRooms() {
        int numOfRoomsVisited = 0;
        Queue<Integer> q = new LinkedList<>();
        int[] visited = new int[size]; // 0 : 방문 X, 1 : 방문 but 선후관계 X, 2 : 방문
        if (before[0] == 0) {
            q.offer(0);
            visited[0] = 2;
        }
        while (!q.isEmpty()) {
            int curNode = q.poll();
            numOfRoomsVisited++;
            for (int nextNode : graph.get(curNode)) {
                if (visited[nextNode] == 2) {
                    continue;
                }
                if (visited[before[nextNode]] != 2) {
                    visited[nextNode] = 1;
                    continue;
                }
                q.offer(nextNode);
                visited[nextNode] = 2;
            }
            int saveNode = after[curNode];
            if (saveNode != 0 && visited[saveNode] == 1) {
                q.offer(saveNode);
                visited[saveNode] = 2;
            }
        }
        return numOfRoomsVisited == size;
    }
}