백준 2001: 보석 줍기

문제 요약

n(1 ≤ n ≤ 100)개의 섬이 m(1 ≤ m ≤ 1,000)개의 다리로 연결되어 있다. 각각의 다리는 서로 다른 두 섬을 연결하고 있으며, 서로 다른 두 섬은 최대 한 개의 다리로만 직접 연결되어 있다. 각각의 다리들의 튼튼한 정도는 서로 달라서, 각각의 다리마다 견딜 수 있는 무게의 제한이 다를 수 있다.

섬들 중, K(1 ≤ K ≤ 14)개의 서로 다른 섬에 각각 한 개씩 보석이 있다. 당신은 1번 섬에서 빈손으로 출발하여 최대한 많은 보석을 줍고 1번 섬으로 돌아오려 한다. 주의할 것은, 보석을 너무 많이 줍다 보면 다리를 건널 때 다리가 무게를 견디지 못하고 무너질 수 있다는 점이다. 따라서 당신은 다리가 무너지지 않는 한도 내에서 보석을 주워야 한다.

한 번 지난 적이 있는 다리와 섬을 여러 번 지날 수 있으며, 보석이 있는 섬을 지날 때에 그 보석을 줍지 않을 수도 있다고 하자.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• 비트마스킹

문제 풀이

각 정점들을 DFS혹은 BFS로 탐색해나가며 개수를 세면 된다. 이때 보석이 있는 정점마다 비트를 할당하여 어느 정점에서 보석을 주웠는지의 상태를 나타내야 한다. 이미 보석을 주운 정점에서는 다시 주울 수 없다. 또한 각 상태마다 정점을 탐색할때가 각각 다르므로 visited배열을 상태와 정점의 2차원 배열로 선언해야 한다.

나는 BFS로 풀었는데, 큐에는 정점, 상태, 개수를 묶어서 push하고, 해당 정점에 보석이 있을 때, 보석을 주워서도 탐색해보고, 줍지 않아서도 탐색해보았다.

각 다리의 가중치를 100x100의 2차원 배열로 선언했을 때 메모리 초과가 났다. 가중치를 저장할 자료구조를 더 효율적으로 구성했고, 보석이 있는 정점의 개수도 많아야 14개이므로, 1차원 배열보다는 map을 사용해주었다.

또한, 1의 정점에 방문할 때마다 최대 개수를 갱신해주었는데, 이때 만약 1의 정점에 보석이 있고, 아직 줍지 않은 상태라면 최대치를 1 증가시켜 주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>

using namespace std;

bool visited[101][1 << 14]
vector<pair<int,int>> weight[101];
map<int, int> cr;
int n, m, k;

int main()
{
	queue<pair<int, pair<int, int>>> q;
	int in, pos, state, ccnt, res = 0, next, val;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < k; i++) {
		scanf("%d", &in);
		cr[in] = i;
	}
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &in, &pos, &state);
		weight[in].push_back({ pos, state });
		weight[pos].push_back({ in, state });
	}
	q.push({ 1, {0, 0} });
	visited[1][0] = true;
	while (!q.empty()) {
		pos = q.front().first;
		state = q.front().second.first;
		ccnt = q.front().second.second;
		q.pop();
		if (pos == 1 && res <= ccnt) {
			res = ccnt;
			if (cr.find(1) != cr.end())
				if (!(state & (1 << cr[1]))) res++;
		}
		for (int i = 0; i < weight[pos].size(); i++) {
			next = weight[pos][i].first;
			val = weight[pos][i].second;
			if (cr.find(pos) != cr.end()) {
				if (val >= ccnt + 1) {
					if (!visited[next][state | (1 << cr[pos])]){
						visited[next][state | (1 << cr[pos])] = true;
						if (state & (1 << cr[pos])) q.push({ next, {state | (1 << cr[pos]), ccnt} });
						else q.push({ next, {state | (1 << cr[pos]), ccnt + 1} });
					}
				}
			}
			if (val >= ccnt) {
				if (!visited[next][state]) {
					visited[next][state] = true;
					q.push({ next, {state, ccnt} });
				}
			}
		}
	}
	cout << res;
	return 0;
}