[Python] BOJ 1516번 - 게임 개발

링크

https://www.acmicpc.net/problem/1516

난이도(solved.ac 참고)

골드3

풀이

이 문제는 위상정렬을 이용한 동적계획법 문제이다.

위상정렬의 알고리즘은 다른 곳에 이미 잘 나와있으므로 짧게 얘기하면 아래와 같은 방식이다.

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
  1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
  2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

tower 배열의 마지막 값은 늘 -1이며 이것은 신경쓸 필요가 없으므로 그 이전 부분까지만 고려한다. tower의 첫번째 값은 해당 인덱스 번째 건물의 완성 시간을 나타내며 두번째 값부터 -1 전까지의 값의 개수만큼 진입차수를 갖고, graph 배열에 넣는다.

시작부터 진입차수가 0이라면 바로 소요시간 배열 times의 값을 최종 결과값인 dp에 우선 박고 큐에 넣은 뒤, 하나씩 빼고 그 큐에 달려있는 그래프들을 순차적으로 돌면서 now 위치를 통해 오는 것과 dp 자체의 값 중 더 큰 값으로 업데이트를 해준다.