[백준] 16947번 서울 지하철 2호선 (Python)

백준 16947 서울 지하철 2호선

비슷한 문제
백준 9466 텀 프로젝트 정리

Cycle detection이 가장 중요한 문제였다. cycle을 탐색하고 이후에 cycle에 있는 노드를 기준으로 다익스트라알고리즘을 활용해 거리를 구하면 되는 문제였다. DFS를 활용해 Cycle 구성하는 노드들을 set에 저장한다. 9466번은 cycle을 구성하는 노드의 개수만 구하면 되기 때문에 BFS를 활용했지만, 구성하는 노드들을 찾아야 하는 경우엔 DFS탐색이 유리하다.

1. 방문했던 노드라면 현재까지의 경로 중에 방문한 적이 있는지 확인한다.
2. 경로에 있다면 해당 경로부터 노드들을 cycle set에 저장한다.
3. 방문한 적이 없다면, 현재 갈 수 있는 모든 노드를 탐색한다. 단, 내가 왔던 노드로 되돌아가지 않도록 이전 노드와 비교한다.
4. DFS 함수 마지막에 path.pop()을 하여 path 초기화를 해준다.

import sys
from collections import deque

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n = int(input().strip())
childs = [[] for _ in range(n + 1)]
visit = [False for _ in range(n + 1)]
res = [0 for _ in range(n + 1)]

cycle = set()

def DFS(ex, i):
    if visit[i]:
        for t in range(len(path)):
            if path[t] == i:
                for j in path[t:]:
                    cycle.add(j)
    else:
        visit[i] = True
        path.append(i)
        for child in childs[i]:
            if child != ex:
                DFS(i, child)
        # pop을 안 해서 고생했다 pop 잊지 말자
        path.pop()

# 그래프 업데이트
for _ in range(n):
    a, b = map(int, input().split())
    childs[a].append(b)
    childs[b].append(a)

# Cycle detection
for i in range(1, n + 1):
    if not visit[i]:
        path = []
        DFS(0, i)

visit = [False for _ in range(n + 1)]
q = deque()
for node in cycle:
    q.append([0, node])
    visit[node] = True

# BFS를 활용한 다익스트라
while q:
    cnt, node = q.popleft()
    for child in childs[node]:
        if not visit[child]:
            visit[child] = True
            res[child] = cnt + 1
            q.append([cnt + 1, child])
print(*res[1:])