[백준] 1516번 - 게임 개발

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

1516번: 게임 개발

 

 

문제 이해

 

첫 번째 행은 N 개의 건물을 지정해 주는 숫자이다.

 

두 번째 행부터는 첫 번째 열은 해당 건물을 만들기 위해 걸리는 시간을 뜻한다.

 

그리고, 두번째 이상 열부터는 해당 건물을 만들기 위해 선행되어야 하는 건물 번호이다.

 

위의 예제에서 보면 2번째 건물의 행을 보면

 

10 1 -1 로 되어있다. (-1은 입력이 끝났다는 표시로 이해하면 된다.)

 

2번째 건물을 짓기 위해서는 최소 10시간이 필요한데,

 

해당 건물을 짓기 위해서는 1번 건물이 지어져 있어야 한다는 뜻이다.

 

1번 건물을 짓는데 필요한 시간은 10시간이므로,

 

2번 건물을 짓는데 필요한 시간은 10 + 10 = 20 시간이 된다.

 

 

 

 

알고리즘 분석

 

스타크레프트를 즐겨했다면, 해당 문제를 이해하는데 매우 쉬울 것이다.

 

하지만, 문제를 이해하는 것과 해당 문제를 푸는 것은 

 

완전히 별개의 문제이다.

 

해당 알고리즘은 위상정렬을 이용해서 풀어야 하는 문제이다.

 

 

 

위상정렬(Topological Sort) 이란?

 

위상 정렬(Topological Sort)은 방향 그래프에서 정점들을 정렬하는 알고리즘이다. 

이 정렬은 그래프 내에서 선후 관계를 가지는 일련의 작업이나 

 

이벤트를 나타내는 정점들을 정렬하는 데 사용된다.

 

위상정렬 알고리즘은 아래의 단계로 설계가 가능하다.

 

1) 진입차수가 0인 정점을 큐에 삽입한다.

* 진입차수 => 특정한 노드가 있을 때, 해당 노드로 들어오는 유향간선의 개수를 의미한다.

* 유향간선 => 방향이 존재하는 간선.

2) 큐에서 원소를 꺼내 연결된 모든 유향간선을 제거한다.

3) 유향간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다.

4) 큐가 빈상태가 될 때까지 2~3번 과정을 지속한다.

 

 

그럼 위의 문제 예시를 가지고 어떤식으로 위상정렬을 적용할 수 있는지 확인해 보자.

 

일단 아래와 같이 방향그래프를 만들어 볼 수 있다.

 

해당 문제를 풀기 위해서는

 

인접노드 리스트, 차수 리스트, 결과 리스트, 필요시간 리스트, 큐가 필요하다.

 

 

인접노드 리스트를 뜻하는 Adjacent 리스트는 

 

index 번호에 대응하는 노드가 어떤 노드를 바라보고 있는지 정보를 가지고 있다.

 

차수 리스트를 뜻하는 Degree 리스트는 

 

index 번호에 대응하는 노드의 진입차수를 보관하는 리스트이다.

 

time list는 각 인덱스에 대응하는 노드의 건물이 지어지기 위한 시간을 의미한다.

 

Result list 는 마지막 정답으로 제출할

 

각 인덱스별 최소시간 정보를 담아둔 배열이다.

 

 

위와 같은 정보가 있을 때, 

 

Degree list에서 차수가 0인 index를 뽑아준다.

 

그다음 Adjacent list에서 해당 index에 대응되는 리스트들의

 

원소를 하나씩 꺼내어 시간 계산을 해주면 된다.

 

 

1. cur = 1인 경우

 

2. cur = 2인 경우

2번 노드에서 시작하는 유향간선은 없으므로 queue에서 빼내주기만 하면 된다.

 

 

 

3. cur = 3인 경우

 

 

큐에 4,5 가 들어가 있지만,

 

해당 노드에서 나가는 유향 간선이 없으므로 큐에서 빼내주기만 하면 된다.

즉 결과 리스트는 아래와 같이 나온다.

 

 

 

 

알고리즘 풀이

 

1. C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N;
vector<int> ver[501];
vector<int> adj[501];
queue<int> que;

int times[501];
int answer[501];
int degree[501];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        int input;
        cin >> input;

        while( input != -1)
        {
            ver[i].push_back(input);
            cin >> input;
        }
    }

    for (int i = 1; i <= N; i++) times[i] = ver[i][0];

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j < ver[i].size(); j++)
        {
            adj[ver[i][j]].push_back(i);
            degree[i]++;
        }
    }

    for (int i = 1; i <= N; i++)
    {
        if (degree[i] == 0) que.push(i);
        answer[i] = times[i];
    }

    while (!que.empty())
    {
        int cur = que.front();
        que.pop();

        for (int i = 0; i < adj[cur].size(); i++)
        {
            int next = adj[cur][i];
            degree[next]--;
            answer[next] = max(answer[next], answer[cur] + times[next]);

            if (degree[next] == 0) que.push(next);
        }
    }
    
    for (int i = 1; i <= N; i++) cout << answer[i] << endl;

    return 0;
}

 

 

 

2. Java

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] result;
    static int[] times;
    static int[] degree;
    static List<Integer>[] ver;
    static List<Integer>[] adj;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        result = new int[N+1];
        times = new int[N+1];
        degree = new int[N+1];
        
        ver = new ArrayList[N+1];
        adj = new ArrayList[N+1];

        for (int i = 0; i <= N; i++) {
            ver[i] = new ArrayList<>();
            adj[i] = new ArrayList<>();
        }

        for (int i = 1; i <= N; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");

            while(stk.hasMoreTokens()) {
                int input = Integer.parseInt(stk.nextToken());

                if (input == -1) break;
                else ver[i].add(input);
            }
        }
        
        for (int i = 1; i <= N; i++) times[i] = ver[i].get(0);
        
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < ver[i].size(); j++) {
                adj[ver[i].get(j)].add(i);
                degree[i]++;
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();

        for (int i = 1; i <= N; i++) {
            if (degree[i] == 0) queue.offer(i);
            result[i] = times[i];
        }
        
        while (!queue.isEmpty()) {
            int cur = queue.peek();
            queue.poll();

            for (int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur].get(i);
                degree[next]--;
                
                result[next] = Math.max(result[next], result[cur] + times[next]);

                if (degree[next] == 0) queue.offer(next);
            }
        }

        for (int i = 1; i <= N; i++) bw.write(result[i] + "\n");
        
        bw.flush();
        bw.close();
        br.close();

    }

}

 

 

3. Python

import sys
from queue import Queue

input = sys.stdin.readline

N = int(input())

adj = [[] for _ in range(N+1)]
vertex = [[] for _ in range(N+1)]

times = [0] * (N+1)
result = [0] * (N+1)
degree = [0] * (N+1)

for i in range(1,N+1):
    data = list(map(int, input().split()))[:-1]
    for j in range(0,len(data)):
        vertex[i].append(data[j])
    
for i in range(1, N+1):
    times[i] = vertex[i][0]
    result[i] = vertex[i][0]

for i in range(1, N+1):
    for j in range(1, len(vertex[i])):
        adj[vertex[i][j]].append(i)
        degree[i] = degree[i] + 1

queue = Queue()

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

while not queue.empty():

    cur = queue.get()

    for i in range(0, len(adj[cur])):
        next = adj[cur][i]
        degree[next] = degree[next] - 1

        result[next] = max(result[next], result[cur] + times[next])

        if (degree[next] == 0):
            queue.put(next)

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