문제
모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.
제한사항
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.
문제를 보고 든 생각
위상정렬이라는 알고리즘을 연습하기 위해서 예제로서 풀어본 문제이다.
강의를 들은 직후에 문제를 살펴보았는데, 역시나 처음이라서 그런지 어떻게 적용을 해야 할지가 떠오르지 않았다.
처음이라서 그렇겠지?
처음엔 못하니까.
물론 위상정렬에 대한 설명, 강의를 들은 게 처음은 아니지만 적용을 해본 경험은 별로 없었던 것 같다.
나의 아이디어
강의에서 들었던 위상정렬이라는 알고리즘의 흐름 그대로 따라서 코드를 적으면 되는 건지 의문이 들었다.
위상정렬이 어떤 과정을 거쳐서 데이터들이 정렬되는지는 어느 정도 이해를 했지만 문제는 풀어본 경험이 별로 없어서 그런지, 이게 정말 위상정렬 알고리즘을 적용시키면 풀리는 문제인가 싶었다.
그래도 강의에서 들었던 위상정렬이 적용되는 문제 상황은 문제의 조건, 상황과 적합했다.
위상정렬이 필요로 되는 문제는 어떤 정해진 조건 아래에 정해진 순서가 있을 때 그것을 조건에 맞게 일직선으로 정렬시켜야 하는 문제이다.
이 문제 역시 그런 문제였다.
결과
나에 대한 불신으로 결국 검색을 해봤다.
검색을 통해 알게 된 내용
신기하게도 이 문제는 기초 수준의 문제여서 그런지, 위상 정렬 알고리즘을 그대로 적용하면 풀 수 있는 문제였다.
검색을 통해 알게 된 풀이
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
graph = [[] for _ in range(n + 1)]
indegree = [0 for _ in range(n + 1)]
for _ in range(m):
start, end = map(int, input().rstrip().split())
graph[start].append(end)
indegree[end] += 1
def topology():
q = deque()
sorted_arr = []
# 진입 차수가 0인 정점을 큐에 넣는다.
for i in range(1, len(indegree)):
if indegree[i] == 0:
q.append(i)
while q:
# 큐 안에서 정점을 뺀 다음, 정답 배열에 넣고 연결되어있던 간선들을 모두 제거한다.
now = q.popleft()
sorted_arr.append(now)
# 간선을 제거한 후 탐색을 했을 때 진입 차수가 0인 것들은 큐에 넣는다.
for i in graph[now]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
return sorted_arr
print(*topology())이 문제는 위상정렬 알고리즘의 흐름을 그대로 적용하면 되는 문제이기에
위상정렬 알고리즘의 흐름을 적어보려고 한다.
1. 진입차수가 0인 정점을 큐에 집어넣는다.
2. 큐가 비어 있지 않은 동안, 큐에 있던 정점을 빼서 그 큐와 연결되어 있던 간선들을 모두 제거한다.
-> 문제를 풀 때는 큐에서 pop된 정점을 정답 배열에 집어 넣어주어야 한다.
-> 간선을 제거하는 건 간단하게 진입 차수가 저장된 배열에서 -1을 해주면 된다.
3. 간선들을 모두 제거한 후에 그래프를 탐색했을 때, 진입 차수가 0이 된 정점이 있다면 큐에 삽입해준다.
4. 2 ~3을 반복한다.
5. 만약 모든 정점을 방문하지 못했는데 끝나버렸다면, 그래프에 사이클이 있다는 것이므로 알고 있자.
-> 위상정렬은 그래프에 사이클이 있다면 사용이 불가능하다.
느낀점
프로그래머스 문제를 풀다가 위상정렬을 알아야 풀 수 있는 문제를 만나서, 위상정렬에 대해 다시 공부한 후 풀어본 기초 문제이다.
몇 번이나 위상정렬에 대한 강의를 들었지만 기억이 하나도 안 나는 내 자신이 대단한 것 같다.
이렇게 멍청할 수가 없다.
그래도 이제는 정리가 됐으니까, 이 기억이 오래 가기를 바란다.
