[BOJ/Gold 1] 백준 2001 보석 줍기(C++)

문제 링크

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

2001번: 보석 줍기

문제

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

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

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

입력

첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 b번 섬이 다리로 연결되어 있는데, 그 다리가 최대 c개의 보석만을 견딜 수 있다는 의미이다. 예를 들어 c가 2라면, 그 다리를 지날 때 보석을 0, 1, 2개 가지고 있어야 한다는 의미이다. 3개 이상의 보석을 가지고 그 다리를 지나려고 하면 다리가 무너진다.

출력

첫째 줄에 주울 수 있는 보석의 최대 개수를 출력한다.

예제 입력 1

6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

예제 출력 1

4

알고리즘 분류

• 그래프 탐색
• 비트마스킹

풀이

섬은 최대 100개가 있지만 보석이 있는 섬은 최대 14개까지이므로, 비트마스킹을 사용하여 어느 섬의 보석을 주운 상태로 다리를 걷고 있는지 확인하면서 탐색할 수 있다.

방문 표시는 visited[100][1<<14]의 2차원 배열로 선언해준다. visited[A][B]가 true라면 어느 섬에서 보석을 주웠는지 나타내는 B 상태에서 A 섬을 지나쳤다는 의미이다.

Island[100]은, Island[A]=B라면 A섬은 B번째 보석 이라는 의미이며, B는 최대 14까지 될 수 있다. 보석이 있는 섬이 최대 14개까지이므로.

변수를 이렇게 선언해주었다면 그래프를 양방향으로 연결하고 BFS를 실행하여, 1번 섬에 도착할 때마다 주운 보석의 개수의 최댓값을 갱신해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 101
#define K_MAX 15
#define LL long long
#define INF 2e9

using namespace std;
int N, M, K;
int Island[MAX];
vector<pair<int, int> > Vec[MAX];
bool visited[MAX][1 << K_MAX];
int answer = -1;

int Bit_Count(int X) {
	if (X == 0) {
		return 0;
	}
	return (X % 2) + Bit_Count(X / 2);
}

void BFS() {
	queue<pair<int, int> > Q;
	visited[1][0] = true;
	Q.push(make_pair(1, 0));
	if (Island[1] != 0) {
		visited[1][(1 << Island[1])] = true;
		Q.push(make_pair(1, (1 << Island[1])));
	}

	while (!Q.empty()) {
		int CurX = Q.front().first;
		int CurJ = Q.front().second;
		Q.pop();

		int CurCnt = Bit_Count(CurJ);
		if (CurX == 1) {
			answer = max(answer, CurCnt);
		}

		for (int i = 0; i < Vec[CurX].size(); i++) {
			int nextX = Vec[CurX][i].first;
			int nextL = Vec[CurX][i].second;
			int nextisJ = Island[Vec[CurX][i].first];
			if (CurCnt > nextL) {
				continue;
			}
			// 보석을 안 줍는다
			if (!visited[nextX][CurJ]) {
				visited[nextX][CurJ] = true;
				Q.push(make_pair(nextX, CurJ));
			}
			// 보석이 있으면 줍는다
			if (nextisJ != 0) {
				bool isPicked = (CurJ & (1 << nextisJ));
				if (!isPicked) {
					int nextJ = CurJ | (1 << nextisJ);
					if (!visited[nextX][nextJ]) {
						visited[nextX][nextJ] = true;
						Q.push(make_pair(nextX, nextJ));
					}
				}
			}
		}
	};
}

int main() {
	FIRST
	cin >> N >> M >> K;
	for (int i = 1; i <= K; i++) {
		int X;
		cin >> X;
		Island[X] = i;
	}
	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		Vec[A].push_back(make_pair(B, C));
		Vec[B].push_back(make_pair(A, C));
	}
	BFS();
	cout << answer << "\n";

	return 0;
}