[백준 16947] 서울 지하철 2호선 (Gold 3)

문제

https://www.acmicpc.net/problem/16947

접근

1. 사이클을 판별한다. 판별 방법은 현재 노드가 이전에 방문한 노드와 연결이 되어있으면 내부 순환이므로 사이클이 있다고 판별한다.

2. 사이클에 해당하는 모든 노드를 저장하고 큐에 넣는다.

3. bfs로 내부 순환 노선도와의 최단 거리를 구한다.

Code

import sys
from collections import defaultdict, deque

sys.setrecursionlimit(111111)

N = int(sys.stdin.readline().strip())
graph = defaultdict(list)
answer = [0] * (N + 1)
visit = [0] * (N + 1)
traced = []
cycle = []


def bfs():
    dist = [-1] * (N + 1)
    for i in cycle:
        dist[i] = 0
    q = deque(cycle)
    while q:
        curr = q.popleft()
        for next_node in graph[curr]:
            if dist[next_node] == -1:
                dist[next_node] = dist[curr] + 1
                q.append(next_node)
    return dist[1:]


def dfs(start, curr, cnt):
    visit[curr] = cnt
    traced.append(curr) # 방문한 노드를 저장
    for next_node in graph[curr]:
        if not visit[next_node]:
            dfs(start, next_node, cnt + 1)
        elif next_node in traced:
            if cnt - visit[next_node] >= 2:
                for i in traced[traced.index(next_node):]:
                    cycle.append(i)
                return
    traced.remove(curr)
    return


for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

for node in list(graph):
    traced = []
    if not visit[node]:
        dfs(node, node, 1)

answer = bfs()
print(*answer)

여담

dfs, bfs 알고리즘 뿐 아니라 dfs를 이용해 사이클을 찾는 방법을 알아야 풀 수 있는 문제. 사이클 문제는 코딩테스트에서 자주 나오는 편은 아니지만 알아두면 웬만한 그래프 문제는 다 풀 수 있을 것 같다.