백준 1516번 게임 개발

문제링크

문제 해설

접근법

방향 있는 그래프이며, 순서까지 있다. 따라서 위상정렬을 생각했다.

위상정렬은 사이클이 존재하지 않는 DAG(Directed Acyclic Graph)에 해당한다.

위상정렬은 bfs, dfs를 이용하여 풀 수 있다.

현재 문제에서는 진입 차수를 고려하여 큐를 활용하여 푼다.

풀이

1.진입, 진출 노드 확인하기

  • 진입 노드란 현재 노드를 가리키는 노드이며, 문제에서 먼저 지어져야 하는 건물을 뜻한다.
  • 진출 노드란 현재 노드가 가리킨 다른 노드이다. 문제에선 현재 건물이 지어져야만 지어질 수 있는 건물을 뜻한다.
  • 입력에서는 현재 노드와 진입 노드를 알려준다. 이를 활용하여 진입 노드의 진출 노드가 현재 노드가 됨을 알 수 있다.
  • 또한 현재 노드의 진입 차수를 확인할 수 있다.

2. bfs

  • 큐를 활용하여 문제 해결한다.
  • 큐에는 (시간, 건물 번호)이 들어간다.
  • 진입 차수가 0인 건물을 큐에 넣어준다.
  • 다음 큐에서 하나씩 꺼내며 현재 건물의 진출 노드를 확인한다.
  • 진출 노드의 기존 시간, 현재 노드의 시간 중 큰 경우를 진출 노드의 시간으로 할당한다.

그림을 통해 확인해보자. 1516번 예제이다.

img

  • 건물 1번만이 진입 차수가 0이다. 따라서 1번을 큐에 넣는다.
  • total배열은 본인의 시간을 제외하고 필요한 최소 시간을 뜻한다.
  • 큐에 하나씩 꺼내니 1번이 나왔다.

img

  • 큐에서 나온 것이 1번이므로 1번의 진출노드들을 확인하며 진입차수를 1씩 낮춘다.
  • 1번의 진출노드인 2,3,4번은 total[2]~total[4]을 1번의 시간인 10으로 변경한다.
  • 그리고 2,3번은 진입 차수가 0이 되었으므로 (시간, 번호)를 큐에 push한다.
  • 큐에서 2가 나왔지만 진출 노드가 없으므로 패스.
  • 큐에서 3이 나올 경우 아래 그림을 보자.

img

  • 큐에서 3이 pop되어 3번의 진출 노드를 보자. 진출노드는 4, 5번이므로 total[4],total[5]은 변경된다.
  • total[4]는 10이지만, total[3]+ 3번의 시간인 14보다 작으므로 total[4] = 14가 된다.
  • total[5] 역시 0, 14 중 큰 수인 14가 할당된다.
  • 4,5번도 진입차수가 0이 되면서 큐에 push된다.
  • 4,5번은 진출노드가 없으므로 큐에서 pop되며 종료.

소스코드

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

// 백준 1516번 게임 개발

using namespace std;

// 위상 정렬
// 연결된 차수가 0인 노드부터 하나씩 삭제.
// 삭제하면서 연결 노드의 총 시간을 기존 시간과 수정된 시간 중 가장 큰 것으로 할당.
// 다시 연결된 차수가 0인 것을 큐에 push

typedef pair<int, int> pi;
int n;
int connect[501];
int total[501];
int cost[501];
vector<int> need[501];

int main() {
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		connect[i] = 0;
		total[i] = 0;
	}

	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
		while (true) {
			int input;
			cin >> input;
			if (input == -1)
				break;
			need[input].push_back(i);
			connect[i]++;
		}
	}


	// 큐는 (비용, 건물 번호) 순서.
	queue<pi> q;

	// 차수가 0인 건물 push
	for (int i = 1; i <= n; i++) {
		if (connect[i] == 0) {
			q.push({ cost[i],i });
		}
	}
	
	while (!q.empty()) {
		int c = q.front().first;
		int from = q.front().second;
		q.pop();

		// 연결된 건물의 총 시간 수정.
		for (int i = 0; i < need[from].size(); i++) {
			int to = need[from][i];
			connect[to]--;
			total[to] = max(total[to], total[from] + c);
			if (connect[to] == 0)
				q.push({ cost[to],to });
		}
	}


	for (int i = 1; i <= n; i++) {
		cout << total[i]+cost[i] << endl;
	}
	return 0;
}