[백준] 1516 - 게임 개발 🎮 / 골드 3 / 위상정렬

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

링크: https://www.acmicpc.net/problem/1516

문제

문제를 요약하자면, 스타크래프트처럼 건물을 짓는데, 순서관계가 있는 경우, 주어진 N개의 건물에 대해 짓는데 걸리는 최소 시간을 출력해야 하는 문제입니다.

 

1) 예제 입출력❄️

예제 입출력

첫 줄에 건물 개수(N)이 5로 주어집니다. 다음 5줄 동안 각 건물을 짓는 데 걸리는 시간과, 해당 건물을 짓기 위해 필요한 건물들이 공백을 구분자로 나오고, 마지막엔 항상 -1로 끝납니다. 해당 예시를 보면 1번 건물은 바로 지을 수 있으므로 그대로 10시간을 출력하면 됩니다. 두번째 건물은 1번 건물을 지어야 지을 수 있기 때문에, 1번 건물을 짓는데 걸리는 10시간과 2번 건물을 짓는데 걸리는 10시간을 합해 20시간을 출력해야 합니다. 3번 건물도 1번 건물을 지어야 지을 수 있고, 10 + 4 하여 14를 출력합니다. 4번 건물은 1번과 3번 건물을 지어야 지을 수 있습니다. 3번은 14 걸리고, 1번은 10이 걸리는데, 3번 건물이 1번을 지어야 지을 수 있으므로, 14 + 4하여 18을 출력합니다. 마지막 5번째 건물은 3번을 지어야 되므로, 14 + 3 하여 17을 출력합니다.

 

2. 핵심 논리☢️

건물은 동시에 여러개를 지을 수 있으므로, 한 건물을 짓기 위해 필요한 건물들 중 가장 오래 걸리는 건물의 시간만 고려하면 됩니다. 핵심은 각 건물을 노드로 봤을 때, 진입차수를 낮춰가며 정렬하는 위상 정렬을 사용하는 것입니다.
(위상 정렬 잘 설명된 링크: https://freedeveloper.tistory.com/390)

 

3. 풀이 코드✅

from collections import defaultdict, deque

N = int(input()) # 건물 개수
ans = [0] * (N+1) # 최종 정답 리스트(각 건물 짓는 총 필요 시간)
cost = [0] * (N+1) # 각 건물 짓는 순수시간
degree = [0] * (N+1) # 진입차수 리스트
Q = deque()

graph = defaultdict(list) # 간선표현 dict ex) graph[1]=[2,3,4]
for i in range(1,N+1):
    temp = list(map(int,input().split())) # 10, 1, -1
    cost[i] = temp[0]
    
    for ele in temp[1:-1]:
        graph[ele].append(i) # ele -> i로가는 방향(i지을 때, ele 필요하다)
        degree[i] += 1 # i의 진입차수 +1

# 초기에 진입차수가 0인 건물들 넣어주기
for i in range(1,N+1): # 진입차수가 0인 노드 Q에 넣어주기, ans에 비용 업데이트
    if degree[i]==0:
        Q.append(i)
        ans[i] = cost[i]

while Q: #Q에 있는 노드들의 간선을 제거하면서, ans값 업데이트
    now = Q.popleft()
    for e in graph[now]:
        degree[e] -= 1
        # 한 건물이 여러건물을 지어야 지을 수 있는 경우, 제일 오래걸리는 건물 짓고, 지을 수 있도록 max로 갱신
        ans[e] = max(ans[e], cost[e] + ans[now])
        if degree[e] == 0: # 진입차수가 0이 되었으면 Q에 넣어주기
            Q.append(e)

print(*ans[1:],sep='\n')

첫 줄에 건물 개수(N)을 입력받습니다. ans(최종 정답 리스트), cost(각 건물 짓는 순수 시간), degree(각 건물 노드의 진입 차수 리스트)를 N+1개의 0으로 된 리스트로 초기화해줍니다. 그리고 graph 변수에 각 건물 번호를 노드로 하고, 의존관계를 표현하여 저장해 줍니다. 예를 들어 2,3,4번 건물은 1번 건물을 지어야 지을 수 있다면 graph[1]=[2,3,4] 처럼 표현됩니다. 

 그 후, 진입차수가 0인 건물들(의존관계없이 바로 지을 수 있는 건물들)을 Q에 넣어주고, ans(정답 리스트)에 각 건물의 cost를 할당해줍니다. 이후 Q에 대해 BFS탐색을 하며, 현재 건물 노드(now)에 대해, 연결된 건물 노드(e)를 반복하며, ans[e] = max(ans[e], cost[e] + ans[now])로 갱신해줍니다. 이 코드의 의미는 건물(e)에 의존적인 건물이 있는 경우, 제일 오래 걸리는 건물 짓고, 건물(e)을 지을 수 있도록 max로 갱신해주는 것 입니다. 그리고, 진입 차수가 0이 된 건물(e)에 대해서는 Q에 append 해줍니다.

 마지막에 ans에 대해 [1:]로 1번 건물부터 *(unpacking)하여 출력하는데, 구분자(sep)를 '\n'으로 하여 한 줄씩 띄어서 출력해주면 정답입니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/1516_%EA%B2%8C%EC%9E%84_%EA%B0%9C%EB%B0%9C.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/
2. 위상 정렬 개념: https://freedeveloper.tistory.com/390