[Python] 백준 1516번 - 게임 개발

문제

• 백준 1516번

최종 코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
times = [0] * (N + 1)
degree = [0] * (N + 1)
buildings = [[] for _ in range(N + 1)]
result = [0] * (N + 1)

for i in range(1, N + 1):
    line = list(map(int, input().split()))

    for j in range(len(line)):
        if line[j] == -1:
            break
        if j == 0:
            times[i] = line[j]
            continue

        buildings[line[j]].append(i)
        degree[i] += 1

que = deque()

for i in range(1, len(degree)):
    if degree[i] == 0:
        degree[i] = -1
        que.append(i)

while que:
    now = que.popleft()
    result[now] += times[now]

    for node in buildings[now]:
        result[node] = max(result[now], result[node])
        degree[node] -= 1

        if degree[node] == 0:
            que.append(node)

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

풀이 과정

---

• 문제의 입력으로 건물의 수와 각 건물을 짓는 데 걸리는 시간, 짓기 위해서 먼저 지어야 하는 건물의 번호가 주어진다
  • 이때, 각 건물을 노드(Node), 건물 짓기의 선후 관계를 방향이 있는 에지(Edge)로 두어 방향 그래프로 생각해 문제를 풀었다
• 또한, 스타크래프트에서 건물을 지을 때 조건의 경우 1 -> 2 -> 3 -> 1과 같이 순환(cycle)이 생기지 않으므로 위상 정렬을 이용하여 문제를 풀어보기로 했다!
  • 처음에는 단순히 진입 차수(degree) 리스트를 이용하여 진입 차수가 0인 노드(건물)를 선택해 소요시간을 더하고 연결된 노드의 차수를 감소시키는 것을 반복하여 각 건물을 짓는데 걸리는 최소의 시간을 구하면 된다고 생각했다
    • 물론 틀린 생각이었지만..

초기 코드

<hide/>
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
times = [0] * (N + 1)
degree = [0] * (N + 1)
buildings = [[] for _ in range(N + 1)]
result = [0] * (N + 1)

for i in range(1, N + 1):
    line = list(map(int, input().split()))

    for j in range(len(line)):
        if line[j] == -1:
            break
        if j == 0:
            times[i] = line[j]
            continue

        buildings[line[j]].append(i)
        degree[line[j]] += 1

que = deque()

for i in range(1, len(degree)):
    if degree[i] == 0:
        degree[i] = -1
        que.append(i)

time_sum = 0
while que:
    now = que.popleft()
    time_sum += times[now]
    result[now] = time_sum

    for node in buildings[now]:
        degree[node] -= 1
        
        if degree[node] == 0:
            que.append(node)

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

문제점

---

• time_sum이라는 하나의 변수에 소요 시간을 계속 더했기 때문에 먼저 지어야 하는 건물이 아님에도 짓는 시간에 추가되는 경우가 생겼다
• 아래의 그림과 같은 경우이다(그림과 글씨가 보기 좋지 못해서.. 죄송합니다 ㅎ..)

검은 숫자: 소요 시간, 빨간 숫자: 예상된 소요 시간, 초록색 숫자: 실제 결과

• 이를 해결하기 위해, time_sum 변수를 사용하여 누적합을 구하는 방식이 아닌 연결된 노드에만 현재 노드의 최소 시간을 더하는 방식으로 변경하였다

# 누적 합으로 최소 시간을 계산하던 부분
time_sum = 0
while que:
    now = que.popleft()
    time_sum += times[now]
    result[now] = time_sum

    for node in buildings[now]:
        degree[node] -= 1
        
        if degree[node] == 0:
            que.append(node)
            
# time_sum 변수 제거 후, 건물을 짓는 조건에 포함된 경우에만 소요시간에 추가
while que:
    now = que.popleft()
    result[now] += times[now]

    for node in buildings[now]:
    	result[node] += result[now]
        degree[node] -= 1
        
        if degree[node] == 0:
            que.append(node)

• 위의 과정으로 해결되었다고 생각하였으나, 아래 그림과 같은 반례가 나왔다

검은 숫자: 소요 시간, 빨간 숫자: 예상된 소요 시간, 초록색 숫자: 실제 결과

• 스타크래프트 게임을 해본 사람도 알 수 있고 문제에서 주어졌듯이 여러 건물을 동시에 지을 수 있다는 것이다
• 즉, 위 그림의 경우에서 알 수 있듯이 1번, 2번 건물은 동시에 지을 수 있으므로 3번 건물을 짓는데 걸리는 최소 시간은 35가 아닌 25이다
• 이를 해결하기 위해서 단순히 먼저 지어야 하는 건물의 최소 시간을 더하는 방식이 아니라 해당 건물의 최소 시간과 먼저 지어야 하는 건물의 최소 시간을 비교하여 둘 중 큰 값을 대입하는 방식으로 변경했다

# 건물을 짓는 조건에 포함된 경우에만 소요시간에 추가
while que:
    now = que.popleft()
    result[now] += times[now]

    for node in buildings[now]:
    	result[node] += result[now]
        degree[node] -= 1
        
        if degree[node] == 0:
            que.append(node)
            
# max() 함수를 이용하여 현재 저장된 값과 새로운 값 중 큰 값을 대입
while que:
    now = que.popleft()
    result[now] += times[now]

    for node in buildings[now]:
        result[node] = max(result[now], result[node])
        degree[node] -= 1

        if degree[node] == 0:
            que.append(node)

• 위 과정을 통해 문제를 해결하였다! 항상 느끼는 점이지만 문제를 풀 때가 아닌 제출을 하고 틀렸을 때 반례를 찾는 경우가 많은 것 같다. 테스트를 할 때 주어진 입력 예제만 볼게 아니라 반례를 찾아보는 습관을 가져야겠다
• 사용했던 반례

# 글의 첫번째 문제점에 해당한 경우
# input
3
10 -1
4 1 -1
100 -1

# output
10
14
100

# 먼저 지어야 하는 건물이 2개 이상일 경우
# input
5
10 -1
20 1 -1
30 2 -1
40 3 5 -1
100 -1

# output
10
30
60
140
100

 

틀린 부분 또는 궁금한 점은 댓글로 남겨주세요! 항상 환영합니다!