[Baekjoon] 1149번: RGB거리

🥅 문제

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

 

🔍 설계

바로 이전 집에서의 색과 다른 색을 칠하기 위해 각 집을 고려할 때마다 큐에서 하나씩 꺼내서 칠할 색을 결정한다. 큐에는 이전 집에서의 색과 비용이 저장되어 있다.

 

하지만, 칠할 수 있는 색에 대하여 모든 경우를 고려할 경우, 메모리 초과가 발생한다.

 

따라서, 어떤 집까지 색을 칠했을 때, 최소 비용을 갱신하고, 그 때의 색과 비용을 큐에 저장하면 메모리 초과 문제를 해결할 수 있다.

 

---

큐를 이용하지 않고, 간단하게 다이나믹 프로그래밍으로 해결할 수도 있다. 아이디어는 같다.

 

👊 풀이1

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

int n, result = 1e9 + 7;
queue<pair<int, int>> q;
vector<vector<int>> cur_min_cost(1000, vector<int>(3, 1e9 + 7));
vector<vector<int>> costs;
vector<int> cost(3);

void bfs() {
	for (int i = 0; i < 3; i++) {
		q.push({ i, costs[0][i] });
	}
	for (int i = 1; i < n; i++) {
		int size = q.size();
		for (int k = 0; k < size; k++) {
			int before_color = q.front().first;
			int before_cost = q.front().second;
			q.pop();
			for (int j = 0; j < 3; j++) {
				if (j != before_color) {
					int cur_color = j;
					int cur_cost = before_cost + costs[i][j];
					cur_min_cost[i][j] = min(cur_min_cost[i][j], cur_cost);
				}
			}
		}
		for (int j = 0; j < 3; j++) {
			q.push({ j, cur_min_cost[i][j] });
		}
	}
	while (!q.empty()) {
		result = min(result, q.front().second);
		q.pop();
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> cost[j];
		}
		costs.push_back(cost);
	}
	
	bfs();
	cout << result << "\n";

	return 0;
}

 

👊 풀이2

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

int n, result = 1e9 + 7;
queue<pair<int, int>> q;
vector<vector<int>> cur_min_cost(1000, vector<int>(3, 1e9 + 7));
vector<vector<int>> costs;
vector<int> cost(3);

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> cost[j];
		}
		costs.push_back(cost);
	}
	
	for (int i = 0; i < 3; i++) {
		cur_min_cost[0][i] = costs[0][i];
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j != k) {
					cur_min_cost[i][j] = min(cur_min_cost[i][j], cur_min_cost[i - 1][k] + costs[i][j]);
				}
			}
		}
	}

	for (int i = 0; i < 3; i++) {
		result = min(result, cur_min_cost[n - 1][i]);
	}

	cout << result << "\n";

	return 0;
}