https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
위상정렬 알고리즘을 알고 이 문제를 풀면 완벽히 이해할 수 있다.
https://solution-is-here.tistory.com/124
[알고리즘] 위상정렬(topological sorting) 파이썬으로 마스터 하기
위상정렬은 순서가 정해져 있는 작업을 수행할 때 차례대로 수행할 수 있도록 도와주는 정렬 알고리즘의 일종입니다. 위상정렬의 수행과정은 크게 3가지로 나눌 수 있습니다. 1. 자기 자신을 가
solution-is-here.tistory.com
첫 번째 줄에 N명의 학생과 비교한 횟수가 주어진다. 두 번째 줄부터는 키를 비교한 두 학생의 번호 A, B가 주어진다.
주어진 학생의 수를 보고 바로 위상정렬의 그래프가 생각나야된다!
위상정렬의 수행과정을 크게 3가지로 나눈 것입니다.
1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음
2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제
3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.
글로 설명하면 어렵기 때문에 코드와 함께 설명하겠습니다.
|
1
2
3
|
nums_people,compare = map(int,input().split())
in_degree = [0] * (nums_people+1)
graph = [[] for _ in range(nums_people+1)]
|
cs |
사람의 숫자와 비교 회수를 입력받은 후, 자신을 선택하는 간선의 개수를 저장하는 in_degree, 자신이 선택하는 정점의 정보가 담긴 graph 리스트를 만들어 줍니다.
-이해가 잘 되지 않는다면 위상정렬 글 다시 보고 오셔야 됩니다!!
|
1
2
3
4
|
for _ in range(compare):
a,b = map(int,input().split())
in_degree[b] += 1
graph[a].append(b)
|
cs |
비교 횟수만큼 반복하는 for 반복문에서 키가 더 큰 사람과 작은 사람을 입력받습니다.
그리고 in_degree [키가 더 작은 사람] += 1을 해줍니다.
*키가 더 작은 사람을 선택당하는 정점으로 이해하시면 됩니다.
그리고 graph [키가 더 큰사람]. append(키가 더 작은 사람)을 해줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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)
|
cs |
진입노드가 0인 정점들을 저장할 height라는 리스트를 만들어줍니다. 1부터 사람의 (숫자 + 1)까지 반복하는 for 반복문에서 진입노드가 0인 정점은 height 리스트에 넣어줍니다.
그 후, height 리스트가 존재할 때까지 반복하는 while반복문에서 height의 가장 작은 정점을 출력해주고 그 정점을 사용해서 정점이 진출한 정점의 정보를 가져옵니다. 진출된 정점의 in_degree 크기를 1 줄이고 만약 in_degree가 0이라면 (진입 노드가 0인 상태) height 리스트에 넣어줍니다.