[골드 3] 백준 16947 - 서울 지하철 2호선 (파이썬)

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

풀이

서울 지하철 2호선은 하나의 순환선과 그 순환선에 연결된 가지 노선들로 구성되어 있음.

각 역은 노드, 연결된 선로는 간선으로 보았을 때

• 입력으로 역들과 연결 정보를 주고,
• 각 역이 순환선으로부터 얼마나 떨어져 있는지(거리)를 출력하는 문제이다.

---

1. 그래프 만들기: 인접 리스트로 저장
2. 순환선 찾기: 리프 노드(leaf, degree==1)들을 반복적으로 제거 → 순환에 속한 노드만 남김
3. BFS로 거리 계산: 순환선 노드들을 시작점으로 BFS 수행 → 거리 계산

N = int(input())
adj = [[] for _ in range(N)]

for _ in range(N) :
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

입력 및 인접 리스트를 구성한다. 역의 개수는 N, 무방향 그래프, 0-indexed로 처리한다.

degree = [len(adj[i]) for i in range(N)]

while True :
    leaf = []
    for i in range(N) :
        if degree[i] == 1 :
            leaf.append(i)
    
    if len(leaf) == 0 :
        break

    for u in leaf :
        degree[u] = -1
        for v in adj[u] :
            if degree[v] != -1 :
                degree[v] -= 1

모든 리프 노드들을 찾아 degree == - 1로 제거 표시한다.

반복하면서 트리 가지 부분을 제거하면 순환에 속한 노드만 남게 된다.

visit = [False] * N
dist = [-1] * N
queue = deque()

for i in range(N) :
    if degree[i] != -1 :
        queue.append(i)
        visit[i] = True
        dist[i] = 0

순환선에 있는 노드들을 시작점으로 큐에 넣고, 거리를 0으로 설정한다.

while len(queue) != 0 :
    u = queue.popleft()
    for v in adj[u] :
        if not visit[v] :
            queue.append(v)
            visit[v] = True
            dist[v] = dist[u] + 1

BFS로 거리를 갱신한다.

코드

# 백준 16947 - 서울 지하철 2호선
# 분류 : 그래프, BFS

from collections import deque

N = int(input())
adj = [[] for _ in range(N)]

for _ in range(N) :
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    adj[u].append(v)
    adj[v].append(u)

degree = [len(adj[i]) for i in range(N)]

while True :
    leaf = []
    for i in range(N) :
        if degree[i] == 1 :
            leaf.append(i)
    
    if len(leaf) == 0 :
        break

    for u in leaf :
        degree[u] = -1

        for v in adj[u] :
            if degree[v] != - 1 :
                degree[v] -= 1

visit = [False] * N
dist = [-1] * N
queue = deque()

for i in range(N) :
    if degree[i] != -1 :
        queue.append(i)
        visit[i] = True
        dist[i] = 0

while len(queue) != 0 :
    u = queue.popleft()

    for v in adj[u] :
        if not visit[v] :
            queue.append(v)
            visit[v] = True
            dist[v] = dist[u] + 1

print(*dist)