[Algorithm] 프로그래머스 - 동굴 탐험

https://school.programmers.co.kr/learn/courses/30/lessons/67260

접근

문제가 좀 긴데… 요약하면 노드 탐색 중에 주어진 방문 순서를 만족하면서 모두 탐색할 수 있는지를 확인하는 문제이다.

그래프 완전탐색이기 때문에 DFS 혹은 BFS로 문제에 접근하면 된다. 나는 BFS 알고리즘을 사용했다.

후수가 선수보다 먼저 나오는 경우에는 탐색 불가능한 경우로 보고, 이후 선수가 나오게 될 때 탐색 가능한 경우로 본다.

즉, 노드에 방문할 때마다 선수를 확인하는 과정과 후수를 확인하는 과정이 연속적으로 이루어져야 한다.

마지막으로, 이 과정에 따라 전체 노드를 탐색했다면 이는 가능한 경우로 탐험 가능한 경우로 보고, 아니면 불가능한 경우로 본다.

소스코드(Java)

import java.util.*;

class Solution {

    private static List<List<Integer>> nodes = new ArrayList<>();
    private static Map<Integer, Integer> from = new HashMap<>();
    private static Map<Integer, Integer> to = new HashMap<>();

    public boolean solution(int n, int[][] path, int[][] order) {

        for(int i = 0; i < n; i++) {
            nodes.add(new ArrayList<>());
        }

        for(int i = 0; i < path.length; i++) {
            nodes.get(path[i][0]).add(path[i][1]);
            nodes.get(path[i][1]).add(path[i][0]);
        }

        for(int i = 0; i < order.length; i++) {
            from.put(order[i][1], order[i][0]);
            to.put(order[i][0], order[i][1]);
        }

        return bfs() == n;
    }

    public static int bfs() {

        int count = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);

        boolean[] visited = new boolean[nodes.size()];
        visited[0] = true;
        count += 1;

        while(!queue.isEmpty()) {
            int q = queue.poll();
            for(int node : nodes.get(q)) {
                    //순서가 없거나 선수를 확인하는 부분
                if((from.get(node) == null || visited[from.get(node)]) && !visited[node]) {
                    queue.offer(node);
                    count += 1;
                    //후수를 확인하는 부분, 후수가 방문되었다면 선수도 방문한다.
                    if(to.get(node) != null && visited[to.get(node)]) {
                        queue.offer(to.get(node));
                        count += 1;
                    }
                }
                visited[node] = true;
            }
        }

        return count;
    }
}