[백준알고리즘] 1005번: ACM Craft -C++

[백준알고리즘] 1005번: ACM Craft -C++

1005번: ACM Craft (acmicpc.net)

1005번: ACM Craft

먼저, 아래의 코드는 비효율적으로 짰다. 아래 코드량만 봐도 왜 이리 긴가 싶을 건데.. 

 

입력의 마지막 조건인 '승리하기 위해 건설해야 할 건물의 번호가 주어진다'는 사실을 몰랐다. 그래서 모든 건물의 건설 시간을 구하는 방안으로 구했다가... 그렇게 작성했던 코드에서 조금 수정하는 방안으로 코드를 작성하다 보니 비효율적으로 됐다. 어제 새벽에 풀다가 너무 졸려서 마무리 짓고 잔 거라..

 

효율적인 방법으로 푸는 건 다음에 풀기를 기대해야겠다.^^

미래의 나 수고해~

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

아래 작성했던 코드는 건설에 필요한 다른 건물 조건이 없는 건물들부터 시작해서, 다른 건물이 필요로 하는 조건이 없는 건물들까지 앞으로 나아가면서 건설 시간을 계산했다. 즉, 문제의 예제 그림과 같은 방향으로 나아가면서 직접 건설 시간을 계산해준 것이다. 

문제의 조건대로 건설시간을 계산하는 방법

따라서 큐를 이용해서 BFS와 유사하게 문제를 풀었다.

 

건설 시간을 결정하기 위해서 큐를 두 개 사용했다. 건설 대기를 하는 큐인 \(building\_queue\)와 그 안에서 가장 건설 시간이 짧은 건물을 선택하기 위한 \(pq\,(priority\,queue)\)를 이용했다. 또한 각 건물이 건설 중인지(\(on\_progress\)), 건설이 완료됐는지(\(built\))를 함께 확인하면서 큐를 관리할 수 있었다.

이렇게 함으로써 건물이 중복되지 않고 건설에 들어가며, 모든 건설 방향으로 동시에 진행하면서 건설 시간을 구할 수 있었다.

 

하지만, 이렇게 했기 때문에 코드도 더러워지고 로직도 복잡해졌다.

 

---

 

사실 목표 건물 번호가 제시된다는 것을 제대로 읽었다면, 이렇게 풀지 않았을 것이다. 목표 건물 번호가 주어지게 된다면 문제가 훨씬 쉽게 풀 수 있기 때문이다.

 

쉽게 풀 수 있는 방법은 아래의 그림과 같다.

쉽게 푸는 방법

바로 목표 건물을 루트로 해서 거꾸로 트리를 만드는 것이다. 이렇게 만든다면, 여러 필요조건을 고려하지 않아도 된다. 루트로부터 내려오는 방향(왼쪽으로 가는 방향)으로 이동할 때 조건이 다 만족하기 때문이다. 그래서 항상 다음 건설할 것만 신경 써주면 되기 때문에, 현재 다음 건설할 것과 이전 건설한 것을 계속 고려해주는 과정이 있는 지금보다 로직도 간단해지고 코드도 간결해지는 것이다.

 

예를 들어, 위의 그림을 통해 보면 원래는 2와 3을 반드시 건설해야 4를 건설할 수 있지만, 역으로 뒤집으면 4를 건설했다면 2와 3을 건설한 것이기 때문에 건설해주면 된다. 다른 건물의 건설 조건을 고려하지 않아도 되는 것이다.

 

---

 

아래는 비효율적인 방법으로 통과한 C++ 코드다. 나중에 고치겠지..!

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

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int test_case;
	std::cin >> test_case;
	for (int t = 0; t < test_case; t++)
		solve();
}

bool can_build(int idx, std::vector<std::vector<int>>& need_buildings, std::vector<bool>& built)
{
	std::vector<int> needs = need_buildings[idx];
	if (needs.empty()) return true;

	for (int n : needs)
		if (!built[n]) return false;
	return true;
}

void solve(void)
{
	int n, k;
	std::cin >> n >> k;

	std::vector<int> time(n);
	for (int& t : time)
		std::cin >> t;
	
	std::vector<std::vector<int>> next_buildings(n);
	std::vector<std::vector<int>> need_buildings(n);
	for (int i = 0; i < k; i++)
	{
		int s, e;
		std::cin >> s >> e;
		next_buildings[s - 1].push_back(e - 1); // 다음 건설 가능 건물
		need_buildings[e - 1].push_back(s - 1); // 건설시 필요 건물
	}

	std::vector<bool> built(n), on_progress(n); // 건설 중 (+ 건설 완료)
	std::queue<std::pair<int, int>> building_queue; // 건설 큐
	for (int i = 0; i < n; i++)
		if (need_buildings[i].empty())
		{
			building_queue.push(std::make_pair(i, time[i]));
			on_progress[i] = true;
		}

	int target;
	std::cin >> target;

	int total_time = 0;
	// 건설 큐 중에서 가장 먼저 건설되는 건물을 찾기 위함
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
	while (!building_queue.empty() && !built[target - 1]) // 아직 target이 건설되지 않았음
	{
		int limit = building_queue.size();
		for (int i = 0; i < limit; i++)
		{
			int idx, time;
			idx = building_queue.front().first;
			time = building_queue.front().second;
			building_queue.pop();

			if (can_build(idx, need_buildings, built))
				pq.push(std::make_pair(time, idx));
			else
				building_queue.push(std::make_pair(idx, time));
		}

		// 건설 큐에서 최소 시간 확인
		int smallest_time, smallest_idx;
		smallest_time = pq.top().first;
		smallest_idx = pq.top().second;
		pq.pop();
		total_time += smallest_time;

		// 건설된 이후 건설 가능한 건물들 건설 큐에 넣음
		built[smallest_idx] = true;
		for (int i = 0; i < next_buildings[smallest_idx].size(); i++)
		{
			int next_idx = next_buildings[smallest_idx][i];
			if (!on_progress[next_idx])
			{
				building_queue.push(std::make_pair(next_idx, time[next_idx]));
				on_progress[next_idx] = true;
			}
		}

		limit = pq.size();
		for (int j = 0; j < limit; j++)
		{
			int remain_time, idx;
			remain_time = pq.top().first;
			idx = pq.top().second;
			pq.pop();

			if (smallest_time < remain_time)
			{
				building_queue.push(std::make_pair(idx, remain_time - smallest_time));
				continue;
			}

			// 최소 시간과 일치하는 시간동안 건설 가능한 건물이 있는 경우
			built[idx] = true;
			for (int i = 0; i < next_buildings[idx].size(); i++)
			{
				int next_idx = next_buildings[idx][i];
				if (!on_progress[next_idx])
				{
					building_queue.push(std::make_pair(next_idx, time[next_idx]));
					on_progress[next_idx] = true;
				}
			}
		}
	}

	std::cout << total_time << '\n';
}