안녕하세요 Dibrary입니다.
이번에는 위상정렬을 사용해야 하는 문제를 정리해보겠습니다.
1516번: 게임 개발
첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부
www.acmicpc.net
예제 입력을 먼저 확인해보겠습니다.
1번째는 10 -1 즉, 10이라는 시간이 소요되고 1번째 노드로 들어오는 노드(먼저 지어져야 하는 건물)는 없다는 것입니다.
2번째는 10 1 -1 즉, 10이라는 시간이 소요되고 2번째 노드로 들어오는 노드는 1노드만 있다는 것입니다.
3번째는 2번째와 같고, 4번째는 4 3 1 -1인데 4라는 시간이 소요되고 4번째 노드로 오는 노드는 3과 1이렇게 2개가 있다는 것입니다.
그려보면 아래와 같습니다.
그러면 우선 1은 10이 걸리고, 2는 1이 지워진 후에 시간이 시작되겠죠? 그러면 10+10이므로 20이 됩니다.
이렇게 해서 1, 2, 3, 4, 5 노드의 시간이 순서대로 10 20 14 18 17 이렇게 나오게 되는 것입니다.
왜 이게 위상정렬과 관련이 있는지 찾아보니,
위상정렬은 진입 차수가 줄어들면 그제사 카운트를 합니다. 따라서, 위 노드에서 1이 지워지면 노드 2와 3에서는 1과 관련된 카운트가 사라지는 것이죠.
코드는 아래와 같습니다.
각 부분별로 코드를 확인해보겠습니다.
먼저 제일 위에 있는 for문은 arr과 indegree를 만드는 것입니다.
arr은 x노드로부터 i노드에 갈 수 있는지 여부를 담아놓는 것입니다. 1이면 갈 수 있고, 0이면 갈 수 없는 것이죠.
indegree는 해당 i노드의 진입 차수 입니다. 이 차수가 0이 되어야 큐에 넣을 수 있죠.
위에서부터 두 번째 있는 for문은 진입차수가 0인 것만 먼저 큐에 넣는 코드입니다.
그런 뒤에 실질적인 작업은 while문에서 진행됩니다.
큐에서 빼고, 해당 x라는 값으로부터 i를 갈 수 있는지 판단하고, 갈 수 있다면 차수를 낮춥니다. 차수가 0이면 당연히 큐에 넣어줘야 하구요.
제가 핵심이라고 적어놓은 부분이 저는 처음에 이해가 안 되었었는데, 진행이 되면서 '소요시간'이 누적되어야 한다는 것이기에 max로 뽑아놓은 것입니다.
일일이 직접 print를 넣어보면서 확인해보면 더 재미나게 익힐 수 있습니다.
'알고리즘 > 문제풀이' 카테고리의 다른 글
| [BOJ][2108번] 통계학 (0) | 2022.09.07 |
|---|---|
| [BOJ][2018번] 수들의 합 5 (0) | 2022.08.19 |
| [BOJ][12891번] DNA 비밀번호 (0) | 2022.08.16 |
| 소수 구하는 방법 (0) | 2022.08.11 |
| [프로그래머스][최소직사각형] - 그리디 문제 (0) | 2022.08.09 |