동굴 탐험

• 유향 그래프에서 사이클의 존재 여부를 찾는 문제의 변형.
• 주어지는 그래프는 트리이다
  • 문제의 “임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며” 라는 조건은 트리가 아니라도 성립할 수 있다. 트리의 조건이 되려면, '최단경로'가 '단순경로'로 바뀌어야 한다
  • 대신, 모든 동굴이 연결되어 있고, 패스의 개수가 n-1개라는 것이 트리의 조건이 된다.
• 루트에서부터 이동할 때, 차일드 노드를 첫 방문하기 위해서는 그 부모 노드를 방문해야 한다. 따라서, 무향 그래프를 부모 노드에서 자식 노드로 가는 엣지만 존재하는 유향 그래프라고 생각해도 상관 없다.
• 결국, 이러한 유향그래프에 order에서 주어지는 엣지들을 추가해서 만든 그래프가, 사이클을 포함하는지를 찾는 문제이다.
• 풀 수 있는 방법은 여러가지이다. 다 O(E)에 풀린다. O(E) = O(|path| + |order|) = O(n)
  • 간단하게 떠오르는 것은 DFS나 BFS를 한번 돌려서 유향 그래프로 변환한 후에, 기본적인 사이클 검출 알고리즘을 쓰는 방법도 가능하다.
    • 기본적인 사이클 검출 알고리은 DFS에 기반한 방식과 Kahn의 위상정렬 알고리즘에 기반한 방식이 있다.
  • 아니면, 유향그래프로 변환하는 과정 없이, 사이클 검출 알고리즘을 약간 변형해서 바로 돌리는 것도 가능하다.
    • Kahn의 위상정렬 알고리즘을 사용할 때에는, 각 노드의 in-degree의 갯수를 세는 과정만 달라진다. 트리이기 때문에, 루트 노드를 제외한 모든 노드는 부모노드로부터만 들어오는 엣지가 있으므로 in-degree는 굳이 엣지들의 갯수를 세며 계산할 필요 없이 그냥 1이다. 인접한 노드들중 어느 노드가 부모노드이고 어느 노드가 자식 노드인지를 굳이 알 필요가 없다. 이 편이 원래 알고리즘 코드를 변형할 부분이 적어보여서 이 방식으로 구현했다
    • DFS로 사이클을 찾을때에는, 이동할때 path의 엣지로 이동하는지 order의 엣지로 이동하는지에 따라, path의 엣지로 이동할 때에는 그 역방향 엣지를 지워주면 된다. 구현은 안해봤다.
• 빼먹기 쉬운 테스트 케이스는, order중에 A방을 방문한 다음 0번 방을 방문해야 하는 것이 있는 경우. 이 경우는 진입 자체를 못하니까 불가능, False를 리턴해야한다

"""Solution code for "Programmers 67260. 동굴 탐험".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/67260
- Solution link: http://www.teferi.net/ps/problems/programmers/67260
"""


def solution(n, path, order):
    graph = [[] for _ in range(n)]
    indegrees = [1] * n
    indegrees[0] = 0
    for u, v in path:
        graph[u].append(v)
        graph[v].append(u)
    for u, v in order:
        graph[u].append(v)
        indegrees[v] += 1

    if indegrees[0] > 0:
        return False
    stack = [0]
    visited_room_count = 0
    while stack:
        u = stack.pop()
        visited_room_count += 1
        for v in graph[u]:
            indegrees[v] -= 1
            if indegrees[v] == 0:
                stack.append(v)

    return visited_room_count == n