백준 1516 : 게임개발 (위상정렬, Python, defaultdict)

문제 :

1516번: 게임 개발

한 달 전까지 못 풀던 문제를 다시 도전해보았다.

 

단순 위상정렬로만 접근해서는 틀린다고 나온다 ㅠㅠ 

 

건물들은 동시에 여러 개를 지을 수 있으므로 의존성 있는 건물 중 오래 걸리는 시간으로 갱신하며 계산되어야 한다..

 

 

---

 

Solution 1 : 2차원 배열

from collections import deque
N=int(input())
val=[0]*N

G=[[0]*N for _ in range(N)]
degree=[0]*N
dq=deque()

for i in range(N):
    tmp=list(map(int,input().split()))
    val[i]=tmp[0]
    for j in range(1,len(tmp)-1):
        G[i][tmp[j]-1]=1
        degree[i]+=1

res=[0]*N
for i in range(N):
    if degree[i]==0:
        dq.append(i)
        res[i]=val[i]        

while dq:
    x=dq.popleft()
    for i in range(N):
        if G[i][x]==1:
            degree[i]-=1
            res[i]=max(res[i],res[x]+val[i])
            if degree[i]==0:dq.append(i)        

for x in res:
    print(x)

res[i]=max(res[i],res[x]+val[i]) << 이 부분이 핵심이다

 

첫 번째 풀이는 2차원 배열에 연결성을 부여해 접근하였다.

 

 

---

 

 

파이썬의 defaultdict 을 이용하면 선행되어야 하는 건물에 의존적인 건물들을 추가하여 풀이할 수 있다.

 

개인적으로 첫 번째 풀이가 맘에 들지만 아래처럼 접근해야 하는 경우도 있을 것 같아 추가한다.

 

 

Solution 2 : defaultdict

from collections import deque, defaultdict
N=int(input())
val=[0]*N

G=defaultdict(list)
degree=[0]*N
dq=deque()


for i in range(N):
    tmp=list(map(int,input().split()))
    val[i]=tmp[0]
    for j in range(1,len(tmp)-1):
        G[tmp[j]-1].append(i)
        degree[i]+=1

res=[0]*N
for i in range(N):
    if degree[i]==0:
        dq.append(i)
        res[i]=val[i]        

while dq:
    x=dq.popleft()
    for y in G[x]:
        res[y]=max(res[y], res[x]+val[y])
        degree[y]-=1
        if degree[y]==0:
            dq.append(y)

for x in res:
    print(x)

 

이런식으로 선행되어야하는 건물: [의존건물들] 로 딕셔너리가 형성된다. 

(defaultdict는 딕셔너리를 리스트처럼 사용할 수 있게 해주는 라이브러리)