[백준] 1516번 : 게임 개발 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1516번: 게임 개발

 

1. 문제 설명

2. 풀이과정

해당 문제를 해결하기 위해선 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다는 문장에 주목해야 한다.

각 건물을 노드라고 할 때, 그래프 형태에서 노드 순서를 정렬하는 위상 정렬 알고리즘을 사용하는 문제라는 것을 알아야 한다.

건물의 수가 최대 500, 시간 복잡도가 2초이므로 시간 제한 부담은 거의 없다.

 

입력 데이터를 바탕으로 필요한 자료구조를 초기화한다.

인접 리스트로 그래프를 표현하고 건물의 생산 시간을 따로 저장한다.

진입 차수 리스트를 그래프에 따라 저장하고, 정답 리스트는 모두 0으로 초기화한다.

위상 정렬을 실행하며 각 건물을 짓는 데 걸리는 최대 시간을 업데이트한다.

 

진입 차수 리스트와 위상 정렬 리스트, 정답 리스트를 업데이트하는 방법

진입 차수 리스트의 값이 0인 인덱스(건물 번호)를 위상 정렬 리스트에 추가하고 해당 인덱스 위치의 정답 리스트 값을

현재 건물에 저장된 최대 시간과 이전 건물에 저장된 최대 시간 + 현재 건물의 생산 시간 중 최댓값으로 업데이트한다.

그리고 진입 차수 리스트의 값은 1 감소시킨다.

 

슈도코드

1. N(건물 수) 입력받기
2. graph(건물 데이터 저장 인접 리스트) 생성하기
3. li(진입 차수 리스트) 초기화하기
4. time(자기 자신을 짓는 데 걸리는 시간 저장 리스트) 초기화하기
5. for 건물의 개수:
   1. info(건물 정보) 입력받기
   2. 자기 자신을 짓는 데 걸리는 시간 리스트에 데이터 저장
   3. 사용할 정보 위치 1로 초기화
   4. while (True):
      1. tmp(1번 정보)
      2. 다음 정보로 변경
      3. 만약 해당 정보가 -1이면(정보 끝): 종료
      4. 그래프에서 해당 정보의 값에 건물 번호 추가
      5. 해당 건물의 진입 차수를 1 증가시킴
6. 큐 생성
7. for N만큼 반복:
   1. 만약 (진입 차수 리스트의 값이 0이면): 해당 건물 번호를 큐에 추가
8. result(정답 리스트) 초기화하기
9. while (큐가 빌 때까지):
   1. 현재 노드 = 큐에서 데이터 가져옴
   2. for 현재 노드에서 갈 수 있는 다음 노드들 탐색:
      1. 다음 노드의 진입 차수를 1 감소시킴
      2. 다음 결과 업데이트 = max(다음 건물에 저장된 시간, 현재 건물에 저장된 시간 + 현재 건물 짓는 시간)
      3. 만약 (다음 노드의 진입 차수가 0이면): 큐에 해당 건물 번호 추가
10. for N만큼 반복: 정답 리스트 값과 해당 건물을 짓는 데 걸리는 시간을 더한 값 출력

반응형

3. 소스코드

import sys
from collections import deque

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

graph = list([] for _ in range(N + 1))
li = [0] * (N + 1)
time = [0] * (N + 1)

for i in range(1, N + 1):
    info = list(map(int, sys.stdin.readline().split()))
    time[i] = info[0]
    index = 1
    while (True):
        tmp = info[index]
        index += 1
        if (tmp == -1):
            break

        graph[tmp].append(i)
        li[i] += 1

queue = deque()

for i in range(1, N + 1):
    if (li[i] == 0):
        queue.append(i)

result = [0] * (N + 1)

while (queue):
    now = queue.popleft()
    for next in graph[now]:
        li[next] -= 1
        result[next] = max(result[next], result[now] + time[now])
        if (li[next] == 0):
            queue.append(next)

for i in range(1,  N + 1):
    print(result[i] + time[i])