백준 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번 같은..
Swift알고리즘
2023. 9. 8. 01:44
