백준(G3) 2252번: 줄 세우기 (파이썬, Python3) + 위상정렬

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

2252번: 줄 세우기

 

위상정렬 알고리즘을 알고 이 문제를 풀면 완벽히 이해할 수 있다.

https://solution-is-here.tistory.com/124

[알고리즘] 위상정렬(topological sorting) 파이썬으로 마스터 하기

첫 번째 줄에 N명의 학생과 비교한 횟수가 주어진다. 두 번째 줄부터는 키를 비교한 두 학생의 번호 A, B가 주어진다.

주어진 학생의 수를 보고 바로 위상정렬의 그래프가 생각나야된다!

 

위상정렬의 수행과정을 크게 3가지로 나눈 것입니다.

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음

2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제 

3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.

 

글로 설명하면 어렵기 때문에 코드와 함께 설명하겠습니다.

 

nums_people,compare = map(int,input().split())
in_degree = [0] * (nums_people+1)
graph = [[] for _ in range(nums_people+1)]

사람의 숫자와 비교 회수를 입력받은 후, 자신을 선택하는 간선의 개수를 저장하는 in_degree, 자신이 선택하는 정점의 정보가 담긴  graph 리스트를 만들어 줍니다. 

-이해가 잘 되지 않는다면 위상정렬 글 다시 보고 오셔야 됩니다!!

 

for _ in range(compare):
    a,b = map(int,input().split())
    in_degree[b] += 1
    graph[a].append(b)

비교 횟수만큼 반복하는 for 반복문에서 키가 더 큰 사람과 작은 사람을 입력받습니다.

그리고 in_degree [키가 더 작은 사람] += 1을 해줍니다.

*키가 더 작은 사람을 선택당하는 정점으로 이해하시면 됩니다.

그리고 graph [키가 더 큰사람]. append(키가 더 작은 사람)을 해줍니다.

 

 

height = []
for i in range(1,(nums_people+1)):
    if in_degree[i] == 0:
        heapq.heappush(height,i)
 
while height:
    m = heapq.heappop(height)
    print(m, end=' ')
 
    for e in graph[m]:
        in_degree[e] -= 1
        if in_degree[e] == 0:
            height.append(e)