백준 16947 파이썬 - 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

문제

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

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

코드

import sys
n = int(sys.stdin.readline())
parent = [0] * (n + 1)
result = [0] * (n + 1)
graphSize = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
    graphSize[a] += 1
    graphSize[b] += 1
while 1 in graphSize:
    for i in range(1, n + 1):
        if graphSize[i] == 1:
            parent[i] = graph[i][0]
            graphSize[i] = 0
            graphSize[parent[i]] -= 1
            graph[parent[i]].remove(i)
while any(parent):
    for i in range(1, n + 1):
        if parent[i] != 0:
            if parent[parent[i]] == 0:
                result[i] = result[parent[i]] + 1
                parent[i] = 0
for i in range(1, n + 1):
    print(result[i], end=' ')

풀이

graphSize는 연결 정보에 나온 숫자들의 횟수를 저장해 놓은 배열이다. 이 값이 1이면 순환선에 포함되지 않는다. graphSize가 1인 곳을 찾아 graphSize가 1인 곳을 0으로 바꿔주고 연결됐던 역의 graphSize 값을 1 줄여준다. parent 배열에 graphSize에서 0이 된 역의 인덱스에 연결돼있던 역의 graphSize 인덱스를 저장해준다.

이렇게 하면 순환선을 뺀 모든 부분들이 graphSize에서 0이 되고 parent에는 순환선에 포함되지 않았던 역들이 연결됐던 역의 인덱스가 저장된다.

그 다음으로 parent에서 0이 아닌 부분을 찾아 거리를 계산한다.

거리를 계산하는 것은 순환선 중 가장 가까운 역에는 0이 있고 그 다음으로 연결된 역 부터 1씩 증가시켜주며 계산한다.