백준 1516 게임 개발 (위상정렬)

1516번: 게임 개발 (acmicpc.net)

1516번: 게임 개발

문제에서 볼 수 있듯이 작업의 순서가 정해져있으며, 그 순서를 정해줘야 하는 알고리즘인 위상정렬을

사용하는 문제였습니다.

위상정렬의 시간복잡도는 O(V+E) (정점의 개수+간선의 개수) 로, 매우 빠른편입니다.

건물의 종류가 최대 500개이기 때문에 완전탐색으로는 해결하기 어려워보입니다.

풀이과정

위상정렬의 과정을 간략하게 적어본다면

 

1. 각 노드마다 진입차수를 저장한다.

여기서 진입차수는 해당 노드에 방문하기 전에 방문해야 할 노드의 개수 입니다.

2. 진입 차수가 0인 노드들을 queue에 넣어준다.

3. queue가 비어있지 않는 동안, queue에서 하나씩 꺼내서 연결된 노드들을 탐색한다.

이때 연결된 노드를 탐색할 때마다 차수를 하나씩 감소시킵니다.

그리고 차수가 0이 되었다면 queue에 넣어주는 과정을 반복합니다.  

 

이렇게 적을 수 있으며,

문제에서 N개의 건물이 각각 완성되는데 걸리는 최소시간을 요구했습니다.

여기서 result[next] = max(result[next], result[now]+time[next]) 를 통해서 업데이트 해줘야 하는데,

최소시간을 구하는데 왜 max를 사용해서 더 큰 값을 저장하는지 의문이 들 수 있습니다.

 

 

예를들어 건물 4를 짓기 위해서 건물 2,3이 먼저 지어져야 한다고 가정해봅시다.

그리고 건물 2가 지어지는데 걸리는 시간이 더 길다고 가정한다면,

건물 3이 먼저 지어지더라도 건물 2가 지어지지 않는 이상 건물 4를 지을 수가 없습니다.

따라서 result[3]+time[4] 보다 더 큰 값인 result[2]+time[4] 가 건물 4를 짓는데 걸리는 시간이 되어야 합니다.

 

코드에 간략한 설명 주석처리를 했습니다.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

// 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 정해주는 알고리즘 ( 위상정렬 )
// 시간복잡도 O(V+E) (정점의 개수+간선의 개수)

int N;
// 각 건물마다 짓는데 걸리는 시간
int getTime[501];
// 차수
int inDegree[501];
// 건물 선후관계
vector < int > v[501];
int result[501];

void solution() {
    // 각 건물마다 최종적으로 걸리는 시간
    queue <int> q;

    // 진입 차수가 0인 건물들을 큐에 삽입
    // 걸리는 시간 바로 넣어줌
    for(int i=0; i<N; i++) {
        if(inDegree[i] == 0) {
            q.push(i);
            result[i] = getTime[i];
        }
    }
    // q에서 하나씩 꺼내보면서 차수를 줄이고,
    // 차수가 0이되면 또 넣어주며 반복한다
    while(!q.empty()) {
        int node = q.front();
        q.pop();

        for(int i=0; i<v[node].size(); i++) {
            int next = v[node][i];
            inDegree[next]--;
            if(inDegree[next] == 0) q.push(next);

            // 더 큰 값으로 업데이트 해야한다
            result[next] = max(result[next], result[node]+getTime[next]);
        }
    }
    for(int i=0; i<N; i++)
        printf("%d\n",result[i]);
}

int main()
{
    int time,prev;
    scanf("%d",&N);
    for(int i=0; i<N; i++) {
        scanf("%d",&time);
        getTime[i] = time;
        while(1) {
            scanf("%d",&prev);
            if(prev == -1) break;
            v[prev-1].push_back(i);
            inDegree[i]++;
        }
    }
    solution();
}