[백준] 게임 개발 : 위상정렬

문제

http://boj.kr/1516

개요

문제를 먼저 읽어보면 눈에 띄는 문장은 최소 시간을 계산해야 한다는 것이고 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다는 것이다.

이는 Topology(위상정렬)의 전형적인 문제 스타일이다.

위상정렬 알고리즘을 요약하자면 그래프의 Indegree가 0인 노드를 그래프에서 제외시키는 과정을 반복적으로 수행하면서 결국에는 그래프 전체 노드를 지우게 되는 방식으로 문제를 해결하는 알고리즘이다.

이 때 그래프는 사이클(Cycle)이 있어서는 안되며 DAG(Directied Acyclic Graph)형태일 때 적용한다.

단순하게 위상정렬의 감을 익히는 용도로는 이 문제를 추천한다

이 문제는 위상정렬에 가중치를 끼얹어 정렬은 물론 최소 경로까지 판단할 수 있어야 하는 문제이다.

그러므로 이 문제는 위상정렬 뿐만 아니라 Top-Down DP를 활용해서 풀 수 있다.

Top-Down DP는 이 글을 확인하자. *추후 업데이트 예정

문제풀이

위상정렬로 풀기 위해서

indeg : 노드의 indegree를 저장한 배열
fromto : 배열의 인덱스를 i라고 할 때 노드 i 에서 도달할 수 있는 다른 노드를 저장한 일종의 인접리스트
prc : 건물(노드)을 짓는데 걸리는 시간을 저장한 배열
ans : 건물(노드)이 최종적으로 완성되기까지 필요한 비용을 저장한 배열

를 선언했다.

풀이 순서는 다음과 같다.

1. 입력을 받으면서 indeg, fromto 그리고 prc를 초기화 한다.
2. 초기화 된 원래 그래프에서 indegree가 0인 부분을 먼저 찾고 ans에 prc 값을 저장한다. 그리고 heapq에 (가격, 노드번호)의 tuple 형태로 heappush 해준다.
3.  이후 while문을 돌며 heappop()으로 추출된 노드의 간선을 하나씩 확인하며 추출된 노드에서 도달 할 수 있는 다른 노드의 indegree를 -1 해준다. (추출된 노드는 이제 그래프에서 제외될 노드이기 때문에 추출된 노드에서 도달할 수 있는 노드의 indegree는 하나 줄어든다.) 
4. 작업을 수행하다가 indegree가 0이 되는 경우에는
   (heappop()된 노드(건물)를 짓는 시간 + 이제 막 indegree가 0이 된 노드(건물)를 짓는 시간) 으로 ans를 갱신한다. 
5. 다음 while문에서 indegree가 0인 노드를 확인해야 하기 때문에 heappush() 해준다. 
6. heappush 해줄 때는
   (indegree가 0이 된 노드(건물)를 짓는 시간 토탈(누적), indegree가 0이 된 노드(건물)번호) 으로 push 해준다.

여기서 나는 우선순위 큐(최소힙)를 사용했는데 그 근거는 다음과 같다.

어떤 건물을 짓는데 걸리는 최소 시간을 구하라는 말은 타겟 건물을 최대한 빠른 시간내에 지어보라는 의미이다.

타겟 건물을 짓기 위해서는 먼저 선행 건물들이 전부 지어져야 한다.

그리고 선행 건물들은 여러가지 방법(경로)으로 지어질 수 있다.

이 때 선행 건물을 짓는 경우의 수 중에서 항상 최소의 시간을 고려하는 경우에는 타겟 건물을 짓는데 걸리는 최소시간을 계산할 수 있다.

heap 자료구조에 들어있는 데이터는 while문과 heappop()을 통해 항상 가중치가 작은 데이터가 우선적으로 추출된다.(반복적으로)

이 반복적인 과정에서 어떤 노드 A의 indegree가 0이 된다면 노드 A, 즉 건물 A를 그 때 지을 수 있다는 이야기 이고

노드 A까지 도달하는데에는 항상 가장 작은 가중치를 사용해서 도달한 것이다.

따라서 이 방법으로 노드 A(건물 A)를 짓게 되면 가장 적은 시간을 들여서 건물을 지을 수 있는 방법이라고 말할 수 있다. 

코드

import sys
from heapq import heappush, heappop

In = lambda : sys.stdin.readline().rstrip()
MIS = lambda : map(int, In().split())

def topo():
  hq=[]
  for i in range(1,N+1):
    if indeg[i]==0:
      ans[i]=prc[i]
      heappush(hq,(prc[i],i))

  while hq:
    p, nd = heappop(hq)
    for pp,x in fromto[nd]:
      indeg[x]-=1
      if indeg[x]==0 and not ans[x]:
        ans[x]=p+pp
        heappush(hq,(p+pp, x))

N = int(In())
indeg=[0]*(1+N)
fromto=[[] for i in range(N+1)]
prc=[0]*(N+1)
ans=[0]*(N+1)
for i in range(1, N+1):
  info=[*MIS()]
  prc[i]=info[0]
  for j in range(1,len(info)-1):
    fromto[info[j]].append((prc[i],i))
    indeg[i]+=1
topo()
print(*ans[1:], sep="\n")