[알고리즘 문제 풀이][위상 정렬] 백준 2252번 - 줄 세우기

백준 2252번 줄 세우기 문제입니다.

(위상 정렬 문제 = Topological Sort)

 

- 문제 설명: https://www.acmicpc.net/problem/2252

- 문제 풀이:

 

BFS, DFS 같은 그래프를 배운 후에, 그래프를 이용한 정렬 문제를 공부해보게 됩니다. 방향성이 있는 그래프를 이용한 정렬을 위상 정렬, Topological 이라고 부릅니다. 문제를 보면, 항상 선후 관계를 줍니다. (줄 세울 때 A가 B보다 먼저 나와야하는 조건이 있다거나, 대학교에서 과목을 듣는데 A 과목이 B 과목의 선수 과목이거나...)

 

백준 문제에 있는 제일 첫번째 예제를 그래프로 표현하면 다음과 같습니다.

1이 3보다 먼저 와야하고, 2가 3보다 먼저 와야합니다. 그러면 1이나 2가 가장 먼저 나오면 되고, 1과 2가 모두 나온 후에 3도 나올 수 있게 됩니다.

 

위상 정렬은 굉장히 간단한 아이디어로 진행이 되는데, indegree 가 0인 (위 그림의 1이나 2처럼 가리키는 화살표가 아무도 없는 경우) 것부터 큐에 넣어 순서대로 꺼내고, 해당 노드를 제거하면서 indegree가 0이 되는 것들을 다시 큐에 넣어줍니다. 

 

node 번호	1	2	3
indegree (화살표가 -> 방향으로 들어오는 개수)	0	0	2

 

1과 2가 indegree가 0이므로 (= 가리킴 당하는 화살표가 하나도 없으므로) 먼저 큐에 넣어줍니다.

 

queue = [1, 2]

 

그 다음에 queue에서 1을 꺼냅니다. 1이 가리키는 다른 노드들을 보면서 indegree 값을 하나 감소시켜 줍니다. 1이 가리키는 3의 indegree 값은 2인데 (1과 2 두 개가 가리키므로) 이때 하나가 감소되므로 1이 됩니다.

node 번호	1	2	3
indegree (화살표가 -> 방향으로 들어오는 개수)	0	0	2 1

 

queue = [2]

 

그 다음에 queue에서 2를 꺼냅니다. 역시 2가 가리키는 노드들을 보면서 indegree 값을 하나 감소시켜 줍니다. 2가 가리키는 3의 indegree 값은 이제 1에서 0이 됩니다. indegree 값이 0이 되었으니 queue에 넣어줍니다!

node 번호	1	2	3
indegree (화살표가 -> 방향으로 들어오는 개수)	0	0	2 1 0

 

queue = [3]

 

마지막으로 queue에 들어있는 3을 꺼내면 됩니다.

 

queue 에서 꺼낼 때마다 result 배열에 저장했다가 한꺼번에 출력해도 되고, 아래 코드는 꺼낼 때마다 print 를 바로 바로 해주도록 코드를 작성하였습니다.

 

※ 본 문제의 코드를 응용하여 아래의 문제를 풀이할 수 있습니다.

(1) https://www.acmicpc.net/problem/14567 백준 14567번 선수과목: 위상 정렬 코드 내부의 큐 (queue) 에 node 와 distance 를 저장하도록 하면 됩니다.

(2) https://www.acmicpc.net/problem/1766 백준 1766번 문제집: 위상 정렬 코드의 큐를 append와 pop 대신 heappush 와 heappop 을 쓰면 됩니다. (import heapq 하고 사용 필요)

 

- 코드: 

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
indegree = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    indegree[b-1] += 1

q = []
for node in range(N):
    if indegree[node] == 0:
        q.append(node)
 
while q:
    cur = q.pop(0)
    print(cur+1, end=" ")
 
    for node in graph[cur]:
        indegree[node] -= 1
        if indegree[node] == 0:
            q.append(node)
print()

위상 정렬을 구현하는 방법은 indegree 방법과 dfs 방법이 있습니다. 본 코드는 indegree 방법을 활용한 예시입니다.

 

- 실수 포인트 & 반례:

1. 시간 초과

Topological Sort를 이용하지 않은 경우, 혹은 이용하였으나 로직에서 잘못된 경우에 시간 초과를 받게 됩니다. 다른 문제와 달리 input, output 이나 배열 생성 등의 작은 포인트에서 시간 초과가 나는 문제는 아닙니다. 전체적인 로직이 맞는 것인지 점검이 필요합니다.

 

2. 아래와 같은 반례를 확인할 수 있습니다.

로직이 잘못되었을 때,

혹은 파이썬 코드에서 초기 배열을 잘못 생성한 경우, ([[]] * N 과 같은 형식) 아래 반례에서 잘못된 답이 나오게 됩니다.

입력
5 4
2 3
1 2
4 2
5 2

정답
1 4 5 2 3

https://www.acmicpc.net/board/view/74119