C++ / 백준 / 1005 / ACM Craft

문제

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

1005번: ACM Craft

문제풀이

vector<vector<int>>order;
vector<vector<int>>foundation;
vector<int>answer;
vector<int>building_time;
vector<int>visit;
int goal;

order벡터는 입력을 받는 벡터이다. 숫자 2개를 입력받으면 order[y][x] 형태인데 y건물을 지으면 x 건물을 지을 수 있다는 의미이다.

foundation[y][x]벡터는 x건물을 지어야 y건물을 지을 수 있다는 의미이다.

foundation[y]행에는 x값이 여러 개가 있을 수 있다.

answer[x]는 x건물을 지었을 때 걸린 총시간을 저장하는 벡터이다.

building_time은 해당 건물을 짓는 시간을 저장하는 벡터이다.

visit은 해당 건물을 방문했는지(해당 건물을 지었는지)를 확인하는 벡터이다.

 

void Init(int size) {
	order = vector<vector<int>>(size + 1, vector<int>(0, 0));
	foundation = vector<vector<int>>(size + 1, vector<int>(0, 0));
	answer = vector<int>(size + 1, 0);
	building_time = vector<int>(size + 1, 0);
	visit = vector<int>(size + 1, 0);
}

테스트 케이스가 있어 답을 여러 번 내야 하므로 답을 내면 벡터를 항상 초기화해야 한다.

벡터들을 전역으로 선언했기 때문에, 건물 개수 N을 입력받을 때마다 Init함수를 실행하여 각 벡터들의 크기를 N+1만큼 생성한다. (초기화)

 

		for (y = 1; y <= K; ++y) {
			cin >> num1 >> num2;
			order[num1].push_back(num2);
			foundation[num2].push_back(num1);
		}

order벡터에서는 num1을 지어야 num2를 지을 수 있으므로 그대로 push 하고

foundation은 2를 지으려면 num1이 필요하다는 것을 의미하는 벡터이므로 foundation[num2]에 num1값을 push 한다.

		for (x = 1; x <= N; ++x) {
			if (foundation[x].size() == 0) {
				answer[x] = building_time[x];
				Build(x);
			}
		}

시작 지점은 입력받거나 항상 정해져 있지 않으므로

아래 그림으로 봤을 때 1, 2부터 시작할 수 있도록 foundation[num]이 비어있는 num들을 찾아 Build함수를 실행한다.

Build함수는 시작 지점 start를 인자로 받는다.

visit[start]가 비어있거나 visit[goal]이 아닐 때만 실행한다.

		for (int o_cnt = 0; o_cnt < order[start].size(); ++o_cnt) {
			next = order[start][o_cnt];
			int max_time = 0;
			for (f_cnt = 0; f_cnt < foundation[next].size(); ++f_cnt) {
				if (!visit[foundation[next][f_cnt]]) {
					break;
				}
				max_time = max(max_time, answer[foundation[next][f_cnt]]);
			}
			if (f_cnt == foundation[next].size()) {
				answer[next] = max_time + building_time[next];
				Build(next);
			}
		}

o_cnt는 order[start]의 사이즈를 세기 위한 변수이다.

order[start] 크기만큼 반복하면서 다음 지점으로 가기 위해 모든 건물들이 지어졌는지를 확인하는 단계이다.

foundation에 있는 요소들을 검사하면서 부족한 건물이 있으면 break를 통해 반복문을 종료한다.

만약 모든 건물이 지어졌다면 다음 건물을 짓는 시간을 저장하고, Build(next)를 해서 다음 건물을 지으러 간다.

 

이 그림에서 보면 3을 짓기 위해 필요한 건물은 1과 2가 있다.

1번 건물부터 짓기 시작한다고 가정해보자.

order[1][0]=3, order[2][0]=3, foundation[3]={1, 2}이다.

1번 건물을 다 지었을 때 확인을 해본다. 3을 짓기 위해 1번, 2번 건물을 다지었나?

-> 2번 건물을 다 못 지었으므로 build함수를 종료한다.

2번 건물을 짓기 시작한다.

2번 건물을 다 지었을 때 확인을 해본다. 1, 2번 건물을 다 지은 것을 확인했다.

그중 짓는데 가장 오래 걸린 건물 시간을 체크하고 answer[3]에 1,2중 최장시간 + 3번 건물을 짓는 시간인building_time[3]을 저장한다.

목표 건물인 goal번 건물을 지을 때까지 반복한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>>order;
vector<vector<int>>foundation;
vector<int>answer;
vector<int>building_time;
vector<int>visit;
int goal;

void Build(int start) {
	if (visit[start] == 0&&!visit[goal]) {
		visit[start] = 1;
		int next = 0;
		int done = 0;
		int f_cnt = 0;
		for (int o_cnt = 0; o_cnt < order[start].size(); ++o_cnt) {
			next = order[start][o_cnt];
			int max_time = 0;
			for (f_cnt = 0; f_cnt < foundation[next].size(); ++f_cnt) {
				if (!visit[foundation[next][f_cnt]]) {
					break;
				}
				max_time = max(max_time, answer[foundation[next][f_cnt]]);
			}
			if (f_cnt == foundation[next].size()) {
				answer[next] = max_time + building_time[next];
				Build(next);
			}
		}
	}
}

void Init(int size) {
	order = vector<vector<int>>(size + 1, vector<int>(0, 0));
	foundation = vector<vector<int>>(size + 1, vector<int>(0, 0));
	answer = vector<int>(size + 1, 0);
	building_time = vector<int>(size + 1, 0);
	visit = vector<int>(size + 1, 0);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T = 0;
	int N = 0, K = 0;
	int y = 0, x = 0;
	int num1 = 0, num2 = 0;;
	int start = 0;
	
	cin >> T;

	while (T--) {
		cin >> N >> K;

		Init(N);

		for (x = 1; x <= N; ++x) {
			cin >> building_time[x];
		}

		for (y = 1; y <= K; ++y) {
			cin >> num1 >> num2;
			order[num1].push_back(num2);
			foundation[num2].push_back(num1);
		}
		cin >> goal;

		for (x = 1; x <= N; ++x) {
			if (foundation[x].size() == 0) {
				answer[x] = building_time[x];
				Build(x);
			}
		}
		cout << answer[goal] << "\n";
	}
}