[백준] 2001번 보석 줍기 C++

문제 출처: https://www.acmicpc.net/problem/2001

2001번: 보석 줍기

 비트마스킹을 활용한 BFS이다.

visited[idx][1 << 14]를 통해 가진 보석마다 방문 배열을 다르게 사용하도록하여 문제를 해결할 수 있다.

1번 섬에서 출발하여 1번 섬으로 도착해야 하므로 일반적으로 시작점을 큐에 push해줄 때 visited도 1로 바꿔주는 방법으로 하면 1번 섬으로 돌아오는 경우를 예외로 처리해주어야 해서 그냥 큐에 push할 때 visited를 바꾸지 않았다.

또한 1번 섬에 보석이 있는 경우가 있다면 시작하자마자 보석을 줍는 경우도 함께 큐에 넣어 주었다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;

struct T
{
	int idx, jewel;
};

typedef pair<int, int>P;

int N, M, K;
int jewelIsland[15];
int visited[101][1 << 14];
int maxV = 0;
vector<P>adj[101];



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

	cin >> N >> M >> K;
	for (int i = 0; i < K; i++)cin >> jewelIsland[i];
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back(P(b, c));
		adj[b].push_back(P(a, c));
	}


	queue<T> q;
	q.push(T{ 1,0 });

	for (int i = 0; i < K; i++) {
		if (jewelIsland[i] == 1) {
			q.push(T{ 1,1 << (i) });
		}
	}

	while (!q.empty()) {
		T curr = q.front(); q.pop();
		int count = 0;
		for (int i = 0; i < K; i++) {
			if ((curr.jewel >> i) & 1)count++;
		}

		if (curr.idx == 1 && visited[curr.idx][curr.jewel] == 1) {
			if (maxV < count)maxV = count;
			continue;
		}

		for (auto next : adj[curr.idx]) {
			//방문여부
			if (visited[next.first][curr.jewel])continue;
			//무게 초과 여부
			if (next.second < count)continue;
			
			int isFlag = 0;
			int isJewel = 0;
			for (int i = 0; i < K; i++) {
				if (jewelIsland[i] == next.first) { 
					isFlag = 1;
					isJewel = i; 
					break;
				}
			}

			//보석섬이든 아니든 보석을 안줍는 경우
			visited[next.first][curr.jewel] = 1;
			q.push(T{ next.first,curr.jewel });
			
			
			if (isFlag != 0) {
				visited[next.first][curr.jewel | (1 << isJewel)] = 1;
				q.push(T{ next.first,curr.jewel | (1 << isJewel) });
			}
		}
	}
	

	cout << maxV;




	
}