[Python] BOJ(백준) 2252번 - 줄 세우기

[Python] BOJ(백준) 2252번 - 줄 세우기

링크

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

난이도(solved.ac 참고)

골드2

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

3 2

1 3

2 3

예제 출력 1

1 2 3

예제 입력 2

4 2

4 2

3 1

예제 출력 2

4 2 3 1

나의 코드

예제 입력들에 대한 출력은 여러가지가 될 수 있다.

예제 입력 2를 보자. 4번 학생이 2번 학생 앞에 서고, 3번 학생이 1번 학생 앞에 선다. 이 뜻은 즉 2번보다 4번이 크고, 1번보다 3번이 크므로 출력 시에 2가 4보다 뒤에, 1이 3보다 뒤에 있기만 하면 된다는 것이다. 나같은 경우는 예제 입력 2번에 대해 3 4 1 2 가 출력되었는데, 어쨌든 2는 4보다 뒤에 있고 1은 3보다 뒤에 있으므로 조건은 충족하였다.

또한 이 문제는 위상 정렬의 기본 개념에서 크게 벗어나지 않는 문제이다.

위에 쓴 대로 생각을 해 보면, 4 2의 경우 2에 대한 진입 차수가 1 증가하는 것과 같다고 생각했다. 왜냐하면, 진입 차수가 0이 될 때 큐에 들어가는데 키가 더 큰 학생이 더 먼저 큐에 들어가면 안되기 때문이다. 그럴 경우 result를 그대로 출력할 때 키가 더 큰 사람이 더 먼저 들어가게 되는 일이 생긴다.

아무튼, 진입차수가 0인 노드를 먼저 큐에 넣은 뒤 큐가 빌 때까지 큐에서 원소를 꺼내서 해당 노드에서 출발하는 간선을 그래프에서 제거하고, 새롭게 진입차수가 0이 된 노드를 큐에 넣는 과정을 반복하는 일반적인 위상정렬의 범주에서 벗어나지 않는 문제이다.

from http://steadily-worked.tistory.com/672 by ccl(A) rewrite - 2021-08-17 14:00:14