문제 설명
•
학생들의 키를 일부만 비교한 결과가 주어질 때, 해당 정보를 활용하여 학생들을 키 순서대로 정렬하는 문제
예제 입력/출력
•
입력1
3 2
1 3
2 3
Plain Text
복사
•
출력1
1 2 3
Plain Text
복사
제약 조건
•
•
문제 풀이
접근1 브루트포스 (완전 탐색) -
접근2 그리디
접근3 DP
•
접근4 위상 정렬 -
그림. 입력1 그래프 예제
•
학생들의 키 비교 관계를 위 그림처럼 단방향 그래프로 나타내면, 위상 정렬을 통해 올바른 순서를 구할 수 있다.
•
위상 정렬을 사용해 입력 1번의 위상 정렬 과정을 따라가보면서 이해해보자.
•
초기 그래프, 진입 차수는 위 그림과 같을 것이다.
•
진입 차수가 0인 노드의 번호를 큐에 삽입한다.
◦
참고로, 문제에서 답이 여러 개인 경우에는 아무 것이나 출력하라고 명시돼있기 때문에 삽입 순서는 고려하지 않아도 된다.
•
큐에서 1번 노드를 꺼내온다.
•
그리고 1번 노드와 연결된 3번과의 간선을 제거하고, 1번 노드와 연결된 3번 노드의 진입 차수를 감소시킨다.
•
큐에서 2번 노드를 꺼내온다.
•
그리고 2번 노드와 연결된 3번과의 간선을 제거하고, 2번 노드와 연결된 3번 노드의 진입 차수를 감소시킨다.
•
3번 노드의 진입 차수가 0이 되었기에 큐에 삽입해준다.
•
큐에서 3번 노드를 꺼내온다.
•
큐가 비었기 때문에 위상 정렬을 종료한다.
•
큐에서 노드를 꺼낸 순서가 이 문제의 정답이 된다. 큐에서 노드를 꺼낸 순서는 1 → 2 → 3 이다.
•
여러 정답이 있을 수 있으며, 문제에서 특정 정렬 순서를 강제하지 않았으므로 큐에서 노드를 꺼내는 순서가 다를 수도 있다.
◦
예제 2번의 위상 정렬 수행 결과로 3 → 4 → 1 → 2 가 나와도 정답 처리가 된다는 이야기이다.
풀이 코드
from collections import deque
# 입력 받기 + 진입 차수 만들기
N, M = map(int, input().split())
adj_list = [[] for _ in range(N + 1)]
degree = [0] * (N + 1)
for _ in range(M):
A, B = map(int, input().split())
adj_list[A].append(B)
degree[B] += 1
# 위상 정렬
q = deque()
for i in range(1, N + 1):
if degree[i] == 0:
q.append(i)
result = []
while q:
cur_node = q.popleft()
result.append(cur_node)
for adj_node in adj_list[cur_node]:
degree[adj_node] -= 1
if degree[adj_node] == 0:
q.append(adj_node)
print(*result)
Python
복사