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

이번에 해결해 볼 문제는 백준에 있는 16947번 서울 지하철 2호선입니다.

---

문제 설명

• 서울 지하철 2호선과 같이 순환선과 지선으로 이루어져 있는 그래프가 있을 때 각 역에서 순환선까지의 거리를 구하는 문제입니다.

문제 해결 아이디어

• 제가 먼저 집중한 포인트는 순환선은 끝이 없지만 지선의 끝은 항상 존재하며 지선이 시작되는 신도림과 같은 역은 3개의 역과 연결된다는 점입니다.
• 순환선과 지선을 구분하기위해 아래와 같은 방법을 사용할 수 있습니다.
  • 연결된 역이 1개인 역 찾기
  • 찾은 역을 지우기
  • 연결된 역이 1개인 역이 없을 때까지 위의 두 방법을 계속 시행 (순환선만 남은 상태)
• 순환선을 찾아나가는 과정에서 연결된 역들을 표시해둠으로써 순환선과의 거리를 알아낼 수 있습니다.

※ 문제를 정확히 읽지 않고 지선이 지하철 2호선의 지선처럼 생겼다고 단정지으면 안됩니다.(2489번: 응급센터 문제에 나와있는 예제 그래프 참고)

문제 해결 코드

import sys

input = sys.stdin.readline

N = int(input())

connect = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
for _ in range(N):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)
    connect[i] += 1
    connect[j] += 1

# 순환선 찾기
visited = [False] * (N + 1)
parents = [0] * (N + 1)
while True:
    flag = 0
    for i in range(1, N + 1):
        if not visited[i] and connect[i] == 1:
            for j in graph[i]:
                if not visited[j]:
                    parents[i] = j
                    connect[j] -= 1
            connect[i] -= 1
            visited[i] = True
            flag += 1
    if not flag:
        break

# 거리 계산
cycle = [0] * (N + 1)
for i in range(1, N + 1):
    if parents[i] != 0:
        length = 0
        now = parents[i]
        while now:
            now = parents[now]
            length += 1
        cycle[i] = length

for c in cycle[1:]:
    print(c, end=" ")