줄 세우기
링크: https://www.acmicpc.net/problem/2252
분류: 그래프 이론, 위상 정렬, 방향 비순환 그래프
레벨: Gold 3
문제
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.
출력
첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.
예제 입력 1
예제 출력 1
예제 입력 2
예제 출력 2
회고
문제를 보자마자 topology sorting의 냄새가 난다.
Topology sorting은 학부 때 잠깐 배웠던 내용이라 이번 문제를 풀면서 다시 학습할 수 있었다.
순서가 정해지고 이 순서를 만족시키면서 정렬을 해야하기 때문에 큐를 사용한다.
이 문제의 핵심은 in-degree를 제거하면서 학생들을 줄 세우는 것이다.
난이도는 무난한 수준인 것 같다.
풀이
우선 graph를 정의해준다.
N개의 학생들의 번호가 주어질 수 있으므로, 각 학생들의 뒤에 올 수 있는 학생 번호를 2차원 list로 표현하여 graph를 정의한다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
a, b = map(int, input().split())
graph[a].append(b)첫 번째 예제를 보면, 1->3, 2->3이 입력으로 주어진다.
이에 대한 graph를 출력해보면 아래와 같이 될 수 있겠다.
맨 앞이 비어 있는 이유는, 0번 번호를 가진 학생은 없기 때문이다.
맨 뒤가 비어 있는 이유는, 3번 번호를 가진 학생보다 키가 큰 학생은 없기 때문이다.
또한, topology sorting은 in-degree(진입차수)를 꼭 파악해야 한다.
여기서 in-degree란, 방향이 자신을 향하는 edge(간선)의 개수이다.
첫 번째 예제에서 1과 2의 in-degree는 0이고, 3의 in-degree는 2이다.
이 in-degree를 계산해야 한다. 1차원 list를 만들어 각 학생의 in-degree를 계산해준다.
그리고 나서 in-degree가 0인 원소를 먼저 큐에 넣어준다.
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
in_degree = [0 for _ in range(N+1)]
q = deque()
for i in range(M):
a, b = map(int, input().split())
graph[a].append(b)
in_degree[b] += 1
for i in range(1, N+1):
if in_degree[i] == 0:
q.append(i)
students = []
while q:
student = q.popleft()
for i in graph[student]:
in_degree[i] -= 1
In-degree가 0인 학생과 연결된 모든 학생들의 연결을 끊어준다.
위 코드의 마지막에 in-degree를 1씩 줄이는 코드가 그것이다.
이런 식으로 연결을 하나씩 끊어 나가면서 in-degree가 0이 되면 그 학생도 큐에 추가한다.
마지막으로 큐에서 뽑았던 원소를 결과 리스트에 넣어주면 끝난다.
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
in_degree = [0 for _ in range(N+1)]
q = deque()
for i in range(M):
a, b = map(int, input().split())
graph[a].append(b)
in_degree[b] += 1
for i in range(1, N+1):
if in_degree[i] == 0:
q.append(i)
students = []
while q:
student = q.popleft()
for i in graph[student]:
in_degree[i] -= 1
if in_degree[i] == 0:
q.append(i)
students.append(student)
print(*students)