[백준 1516] 게임 개발

[BanApp]

import sys
from collections import deque

n = int(sys.stdin.readline())

arr = deque([]) #건물을 지을 조건들을 담을 배열

for i in range(n):
    x = deque(map(int,sys.stdin.readline().split()))
    x.append(i+1) #본인이 몇번째 건물인지 기억하도록 함
    arr.append(x)

visited = [False for _ in range(n+1)] #방문 처리
ans = [0 for _ in range(n+1)] #최종 정답이 담길 배열

while arr:
    x = arr.popleft()

    if len(x) == 3: #다른 건물이 먼저 지어지는 선수 조건이 필요하지 않은 건물들
        visited[x[-1]] = True
        ans[x[-1]] = ans[x[-1]] + x[0]

    else:
        value = x.popleft()
        cnt = []
        for i in x:
            if i == -1:
                break
            elif visited[i] == True:
                cnt.append(i) # 지어진 건물중 걸리는 시간의 최대값을 알기 위해 cnt 배열에 담아둠
            elif visited[i] == False:
                break

        if len(cnt) == len(x) - 2:
            key = 0
            for j in cnt:
                if ans[j] > key: #조건을 만족해야하는 지어진 건물들중 가장 시간이 오래 걸리는 건물을 찾는 과정
                    key = ans[j]
            ans[x[-1]] = key + value
            visited[x[-1]] = True

        else:
            x.appendleft(value) #만약에 조건을 만족하지 않을 경우 다시 원래대로 배열을 만들어주고
            arr.append(x) # 정상화된 배열을 다시 arr에 넣는다. 나중에 탐색하기 위해서

for i in range(1,len(ans)):
    print(ans[i])

오늘 오픈소스 시간에 찬희짱께서 재밌는 문제를 푸는것 같아보여서 집 와서 저도 한번 해봤습니다.
단순 DP문제라고 생각하고 접근해봤습니다.

큰틀은 BFS를 이용했는데 가장 먼저 조건을 만족하면 그것이 도달할수 있는 최소값(가장 최적의 값)임이 보장된다.
한번 값이 나온애들은 visited 배열에 방문 처리를 해줘서 다시 방문하는 일이 없도록 한다. 이는 건물이 지어진 경우라고 볼 수 있다.
즉 visited 배열이 False면 건물이 아직 안 지어짐, visited 배열이 True 이면 건물이 지어진 거라고 볼 수 있다.
그리고 지어진 건물의 조건들은 arr에 다시 넣지 않고 조건을 만족하지 못한 애들은 다시 arr에 넣어준다.
다만 이렇게 하면 배열의 순서가 망가지기 때문에 arr의 원소배열의 맨 뒤에 본인이 몇번째 건물인지 알 수 있도록 값을 넣어준다.
이렇게 해서 arr배열이 빈 배열이 되면 종료하고 ans를 출력한다.

쉬운 DP 문제 == BFS 문제 거의 맞는 말인것 같다.

다만 이게 가장 빠른 방법은 아니기에 추천 드리지는 않습니다.
실제로도 가장 빠른 정답을 맞춘 사람은 pypy3로 130ms 정도 걸리는거 이걸로는 200ms 걸립니다.
보자마자 이렇게 풀어야겠다 라고 떠올랐을뿐..
정해는 위상정렬로 푸는 것이라고 합니다..