[프로그래머스] 동굴 탐험 / 2020 카카오 인턴십 / python

이 문제의 포인트는 각각의 노드마다 부모 노드들을 저장하는 그래프를 만들고 사이클이 존재하는지 검사하는 것이다.
예를 들어, 만약 1이라는 노드가 부모를 타고 올라가다가 어떤 노드의 부모가 자신인 1이게 되면 사이클이 존재한다는 의미이기 때문에 모든 방을 탐방하지 못할 수도 있다.

우선 각각의 노드마다 부모 노드들을 저장하는 need_dict를 만들었는데 과정은 아래와 같다.

1. 처음에 주어진 path로 각 노드끼리 연결되는 정보를 양방향으로 link_dict에 저장한다.
2. link_dict에 노드들을 돌면서 각각의 노드마다 자식 노드들이 자신을 가리키는 정보를 need_dict에 저장한다.
3. 주어진 order 정보를 need_dict에 추가한다.

이제 need_dict에 사이클이 존재하는지 확인해보자. 사이클이 존재한다면 탐방에 실패한 것이다.

• 사이클은 need_dict를 dfs로 도는데 방문한 노드들은 방문 체크와 이하 노드 사이클 존재 여부를 확인했다는 체크를 해준다.
• 방문 체크가 되어있는 노드를 만나면 사이클이 존재하는 것이다.
• 방문 체크가 되어있는 노드를 만나지 않고 리프 노드까지 갔다면 해당 노드의 방문 체크를 False로 바꿔주고 이전 노드로 하나씩 올라가며 dfs를 진행한다.
• 이 때 방문 체크와는 별개로 해당 노드 이하 노드의 사이클 존재 여부를 확인했다는 또 다른 체크는 True 상태로 내버려둔다.
  • 그러면 다른 노드에서 해당 노드에 방문했을 때 이전에 이미 처리했던 똑같은 작업을 다시 하지 않아도 된다.
  • 시간 복잡도를 줄일 수 있다.

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

link_dict = defaultdict(list)
need_dict = defaultdict(list)


def solution(n, path, order):
    for a, b in path:
        link_dict[a].append(b)
        link_dict[b].append(a)

    set_need_dict(0, -1)

    for a, b in order:
        need_dict[b].append(a)

    visited = [False for _ in range(n)]
    recur = [False for _ in range(n)]
    for i in range(n):
        if is_cycle(i, visited, recur):
            return False

    return True


def set_need_dict(node, parent_node):
    for next_node in link_dict[node]:
        if next_node == parent_node:
            continue
        need_dict[next_node].append(node)
        set_need_dict(next_node, node)


def is_cycle(node, visited, recur):
    if visited[node]:
        return True
    if recur[node]:
        return False

    visited[node] = True
    recur[node] = True

    for parent_node in need_dict[node]:
        if is_cycle(parent_node, visited, recur):
            return True

    visited[node] = False
    return False