[백준] 16947번: 서울 지하철 2호선

문제

백준 - 16947번: 서울 지하철 2호선

분석

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구하는 문제이다.

주어진 그래프에서 사이클을 추출하기 위해 Union Find를 사용했다.
연결하려는 두 노드가 이미 같은 부모를 가지면 사이클을 가진다고 판단하고 dfs를 사용하여 사이클에 해당하는 노드들을 얻었다.
마지막으로 사이클에 해당하는 노드들을 모두 큐에 넣고 bfs를 진행하여 사이클로 부터 각 역과의 거리를 구할 수 있었다.

dfs를 진행할 때 모든 path의 경우를 따져야 되기 때문에 방문처리 변형으로 dfs를 한번 진행하고 빠져나오면 재방문이 가능하게 했다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**5)
from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
uf = [i for i in range(n+1)]
def find(x):
    if x == uf[x]:
        return x
    uf[x] = find(uf[x])
    return uf[x]

def union(x, y):
    X = find(x)
    Y = find(y)
    if X != Y:
        uf[X] = Y

def dfs(x, dst, path):
    global cycle
    visited[x] = True
    path.append(x)
    if x == dst:
        cycle = path[:]
        return
    for nx in graph[x]:
        if not visited[nx]:
            dfs(nx, dst, path)
    visited[x] = False
    path.pop()

def bfs():
    lst = list(cycle)
    for x in lst:
        visited[x] = True
    q = deque(lst)
    while q:
        x = q.popleft()
        for nx in graph[x]:
            if not visited[nx]:
                visited[nx] = True
                dist[nx] = dist[x] + 1
                q.append(nx)

cycle = []
for _ in range(n):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    if find(a) != find(b):
        union(a, b)
    else:
        visited = [False]*(n+1)
        dfs(a, b, [])

dist = [0]*(n+1)
visited = [False]*(n+1)
bfs()
print(*dist[1:])

끝으로..

유니온 파인드, bfs, dfs 를 모두 쓴 문제였다. 복합적인 알고리즘을 이용해서 문제를 풀어봤는데, 더 많은 문제를 풀어서 대비해야겠다.