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

문제:www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

 

import sys
N=int(input())
parent=[0]*(N+1)
ans=[0]*(N+1)
graph=[[] for _ in range(N+1)]
graphSize=[0]*(N+1)
for _ in range(N):
    a,b=map(int,input().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:
                ans[i]=ans[parent[i]]+1
                parent[i]=0
for i in range(1,N+1):
    print(ans[i],end=' ')​

 

6
1 2
3 4
6 4
2 3
1 3
3 5

밑의 예시의 데이터는 다음과 같다.

위와 같이 graphSize에서 1의 값이 있는 것을 계속 삭제하면 위와 같이 나온다. 

 

그리고 나서 순환선 사이의 거리를 출력해야 하는데 이와 관련된 로직은 다음과 같다.

우선 처음에 부모가 0이 아닌 값을 찾는다. 그리고 그 부모의 부모가 0이면 순환선 거리 계산을 한다.

이렇게 짠 이유는 우선 순환선의 부모값은 0이기 때문에 순환선의 처음에 시작하는 역의 부모의 부모 값은 무조건 0이기 때문이다.

간단하게 위의 예를 가져와서 설명해보자.

우선 처음에

parent[4]는 0이 아니기에 처음 if문에 적합하다.

그리고 다음 if문에서 parent[3]은 0이기 때문에 ans[4]=1의 값을 가진다. 

이런식으로 다 돌면 답이 나온다.