백준 2623: 음악프로그램 (위상정렬Topology Sort / with Swift)

위상정렬 문제이다.

생각보다 헷갈릴 만한 포인트가 많이 들어가있는 문제이다.

 

1. 같은 숫자가 여러 번 나오는데, 이에 대한 처리를 어떻게 해줘야하는가?

2. 순서를 정하는 것이 불가능한 경우가 어떻게 생기는가?? 

 

 

먼저 1번의 경우에는, 

1 -> 3

2 -> 3 -> 4

2 -> 3 -> 5

과 같이 하나의 점으로 들어오는 경우가 많은 와중에, 2 -> 3 과 같이 동일한 것이 여러 번 나올 때는 나올 때마다 graph[2].append(3)해주면 된다. 

 

이유?

어차피 위상정렬을 수행하면서 2가 queue에서 나오고, 2에서 들어가는 점들에 대한 indegree를 1씩 감소시킬텐데, 그 때 알아서 겹쳐서 제거될 것이기 때문! ( Graph가 set이 아닌 Array 형태이므로 걱정할 것 없음)

 

 

 

2번 같은 경우에는, 

1 -> 2 와 2 -> 1이 동시에 존재하여 Cycle이 존재하는 경우.

 1 -> 2 , 2 -> 5, 5 -> 1 과 같이 3개의 점이 돌고돌아 Cycle이 존재하는 경우.

이처럼 어떻게든 Cycle이 존재한다면, 그 Cycle에 포함되는 점들은 어떻게든 indegree가 0이 될 수 없고, Queue에 들어갈 수 없기 때문에,

 

최종적으로 Queue에 들어갔다 나온 숫자들의 수가 총 node 갯수인 n보다 작다면, 순서를 정하는 것이 불가능하다고 판단하면 된다!