Programmers - 동굴 탐험[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/67260

코딩테스트 연습 - 동굴 탐험

 

문제 설명

오지 탐험가인 프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다.

탐험에 앞서 이 지하 동굴의 지도를 손에 넣은 프로도는 다음과 같이 탐험 계획을 세웠습니다.

1. 모든 방을 적어도 한 번은 방문해야 합니다.
2. 특정 방은 방문하기 전에 반드시 먼저 방문할 방이 정해져 있습니다.
   2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다.
   2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다.
   2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다.
   2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다.

위 계획 중 2-2, 2-3, 2-4는 순서를 지켜 방문해야 하는 두 방의 쌍이 A → B(A를 먼저 방문하고 B를 방문함) 형태로 유일함을 의미합니다. 즉, 프로도는 아래와 같은 형태로 방문순서가 잡히지 않도록 방문 계획을 세웠습니다.

• A → B, A → C (방문순서 배열 order = [...,[A,B],...,[A,C],...]) 형태로 A를 방문 후에 방문해야 할 방이 B와 C로 두 개 또는 그 이상인 경우
• X → A, Z → A (방문순서 배열 order = [...,[X,A],...,[Z,A],...]) 형태로 A를 방문하기 전에 방문해야 할 방이 X와 Z로 두 개 또는 그 이상인 경우
• A → B → C (방문순서 배열 order = [...,[A,B],...,[B,C],...) 형태로 B처럼 A 방문 후이면서 동시에 C 방문 전인 경우

그리고 먼저 방문해야 할 방과 나중에 방문할 방을 반드시 연속해서 방문해야 할 필요는 없어 A방을 방문한 후 다른 방을 방문한 후 B방을 방문해도 좋습니다.

방 개수 n, 동굴의 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path, 프로도가 정한 방문 순서가 담긴 2차원 배열 order가 매개변수로 주어질 때, 프로도가 규칙에 맞게 모든 방을 탐험할 수 있을 지 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• n은 2 이상 200,000 이하입니다.
• path 배열의 세로(행) 길이는 n - 1 입니다.
  • path 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
  • 두 방 A, B사이를 연결하는 통로를 나타냅니다.
  • 통로가 연결하는 두 방 번호가 순서없이 들어있음에 주의하세요.
• order 배열의 세로(행) 길이는 1 이상 (n / 2) 이하입니다.
  • order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
  • A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.

 

입출력 예

 

문제 풀이

Lv4 문제로 위상 정렬을 활용한 접근으로 문제를 풀었다. 이 문제는  위상정렬을 활용한 사이클 판별 문제라고 볼 수 있다.  참고 : 위상 정렬

 

해당 문제의 설명은 양방향 그래프라고 설명하고 있지만 문제 설명에서 "이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다."와 "서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다.임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다."라는 조건이 있기 때문에 루트 노드가 0인 단방향 트리 구조를 갖는 그래프라고 생각해도 무방하다. 

 

path의 경우 방향의 순서를 고려하지 않고 입력되기 때문에 트리구조라는 가정하에 BFS를 통해서 path에 대한 단방향 그래프를 생성할 수 있다.

 

이후 생성된 단방향 그래프에서 order노드를 추가하게 되면 그래프에 사이클이 생기거나 생기지 않을 수 있는데 위상 정렬을 활용하면 그래프의 집입 순서를 고려하여 모든 노드를 순회하게 된다. 이때 사이클이 없는 그래프의 경우 모든 노드의 진입 순서를 고려하여 순회 할 수 있지만, 사이클이 있는 경우 순서를 고려할 수 없게 된다. 즉 진입 순서를 고려하지 못하기 때문에 모든 노드를 순회 할 수 없게된다. 

 

정리하자면 단방향 그래프에서 사이클이 없다면 위상정렬을 통해 order의 순서에 위배되지 않도록 모든 방을 적어도 한 번은 방문할 수 있어 답은 True이고, 사이클이 생긴다면 진입 순서를 고려할 수 없기 때문에 모든 방을 방문할 수 없어 답은 False가 된다.

구현 코드

from collections import deque

# 위상 정렬 함수
def topology_sort(graph, indegree):
    q = deque([0]) # 큐 기능을 위한 deque 라이브러리 사용
    count = 0
    # 큐가 빌 때까지 반복
    while q:
        count += 1
        # 큐에서 원소 꺼내기
        now = q.popleft()
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)
    return count

def bfs(n, graph, indegree):
    new_graph = [[] for i in range(n + 1)]
    visited = [False] * n
    visited[0] = True
    q = deque([0])
    while q:
        cur_node = q.popleft()
        for node in graph[cur_node]:
            if not visited[node]:
                visited[node] = True
                new_graph[cur_node].append(node)
                indegree[node] += 1
                q.append(node)
    return new_graph, indegree

def solution(n, path, order):
    # 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
    graph = [[] for i in range(n + 1)]
    # 모든 노드에 대한 진입차수는 0으로 초기화
    indegree = [0] * (n + 1)
    # 양방향 그래프 생성
    for a, b in path:
        graph[a].append(b)
        graph[b].append(a)
    # bfs를 통해 단방향 그래프 생성
    new_graph, indegree = bfs(n, graph, indegree)
    for a, b in order:
        new_graph[a].append(b) # 정점 A에서 B로 이동 가능
        # 진입 차수를 1 증가
        indegree[b] += 1
    #모든 노드에 대한 위상 정렬이 가능하면 True 아니면 False 반환
    if n == topology_sort(new_graph, indegree):
        return True
    else:
        return False