백준 2001 보석줍기 C++

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

2001번: 보석 줍기

 이 문제는 1번 섬에서 출발하여 섬 사이를 잇는 다리를 통해 이동하면서 1번 섬으로 돌아올 때, 가능한 가장 많은 보석의 수를 구하는 문제이다. 이 때, 다리에는 견딜 수 있는 보석의 수가 주어진다. 예를 들어, 어떤 다리의 이 숫자가 3이라면 이 다리를 건널 떄 가지고 있는 보석의 개수가 0, 1, 2, 3이라면 지날 수 있고 이보다 클 경우는 지날 수 없다. 그렇기 때문에 이 문제의 핵심은 이 각 보석 수에 대한 상황을 잘 다루는 것이다.

 하지만, 이 문제는 단순히 보석의 개수만 신경써서는 안되는 문제이다. 몇 번 보석을 가지고 있는지가 중요하다. 예를 들어, 3번 섬으로 이동하는 경우가 있다고 하자. 단순히 보석의 개수만 신경을 쓴다면 1반 보석만을 가지고 가는 경우나 2번 보석을 가지고 가는 경우나 같은 경우로 취급된다. 이로 인해 다양한 경우를 고려할 수 없게 될 것이다. 그렇기 때문에 단순한 보석의 개수가 아닌, 어떤 보석들을 가지고 있는지가 중요하다. 그런데, 이를 단순히 배열로만 표현한다면, 최악의 경우(섬은 최대 개수인 100개, 보석이 최대 개수인 14개인 경우)는 bool check[101][2][2][2][2][2][2][2][2][2][2][2][2][2][2]; 가 될 것이다. 그렇기 때문에 다른 방법을 고려해야 하는데, 이 떄 적절한 방법이 바로 비트마스킹이다.

 비트마스킹을 이용하면 위의 check 변수를 단순히 bool chck[101][보석최대소지]; 가 된다. 그렇다면 비트마스킹을 어떻게 이용할 거인가. 각 보석을 소지했을 때를 2진수로 나타내자. 총 보석이 5개이고 아무 보석도 가지고 있지 않을 때는 00000( = 0), 1번 보석만 가지고 있을 때는 00001 ( = 1), 3번 보석만 가지고 있을 때는 00100( = 4), 1, 2, 4번 보석을 가지고 있을 때는 01011과 같이 나타낼 수 있다. 그리고 이런 방법은 바로 비트단위 연산자를 이용하면 가능하다.(https://www.learncpp.com/cpp-tutorial/bitwise-operators/) 그리고 이를 이용한 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#pragma warning(disable:4996)

using namespace std;

#define MAX 101
#define START 1

int islandNum, bridgeNum, treasureNum;	// 각각 입력 받을 섬의 수, 다리 수, 보석 수
int hasTreasure[MAX];	// 각 섬이 가지고 있는 보석(기본값 = -1), 예) hasTreasure[5] = 2 => 5번 섬이 2번 보석 가지고 있음
bool visited[MAX][17000];	// 예) visited[2][n] = true => 2번 섬을 가지고 있는 보석 경우가 n일 때 방문하였음(true)
vector<pair<int, int>> bridges[MAX];	// a번 섬을 bridges[a].first 섬과 이어져있고, 이 다리의 보석 허용치는 bridges[a].second이다.

// 보석의 경우 x가 주어졌을 때, 총 몇 개의 보석이 있는지를 return하는 함수
// 즉, 비트의 1의 개수를 return하는 함수
int BitCount(int x)
{
	if (x == 0) 
		return 0;

	return (x % 2) + BitCount(x / 2);
}

int Check()
{	
	// 최대 보석 개수를 저장할 변수
	int maxTreasuure = 0;
	
    // 큐를 이용하여 탐색
    // 가장 먼저 1번 섬에서 (보석이 있든 없든) 보석을 안들고 출발
	queue<pair<int, int>> q;
	q.push({ START, 0 });
	visited[START][0] = true;
	
    // 만약 1번 섬에 보석이 있을 경우, 그 보석을 들고 출발하는 경우도 고려해야 한다.
	if (hasTreasure[START] > -1)
	{
		int startTreasure = (1 << hasTreasure[START]);	// 비트 연산자로 보석 번호 기록
		q.push({ START, startTreasure });
		visited[START][startTreasure] = true;
	}

	// 큐가 비지 않으면 계속 반복한다. 
	while(!q.empty())
	{	
    	// 큐에서 현재 섬, 현재 보석 소지 상황, 보석 개수를 알아낸다.
		int curIsland = q.front().first;				// 현재 섬
		int curTreasures = q.front().second;			// 현재 보석 소지 상황
		int curTreasureNum = BitCount(curTreasures);	// 현재 보석 소지 개수
		q.pop();	// 큐를 pop 하지 않으면 무한히 반복한다. 
	
    	// 만약 현재 섬이 1번 섬이라면 보석의 최대 개수를 갱신할 수 있는지 확인한다.
		if (curIsland == START)
		{
        	// 만약 보석 최대 개수를 갱신할 수 있는 상황이라면 갱신
			if (maxTreasuure < curTreasureNum)
				maxTreasuure = curTreasureNum;
		}
		
        // 현재 섬과 이어져 있는 다리를 모두 체크한다.
		for (int i = 0; i < bridges[curIsland].size(); ++i)
		{	
			int nxtIsland = bridges[curIsland][i].first;	// 현재 섬과 연결된 섬
			int capacity = bridges[curIsland][i].second;	// 현재 섬과 연결된 다리
			
            // 만약 현재 가지고 있는 보석의 개수가 다리의 허용 수치를 넘어버리면 
            // 어차피 못 건너가기 때문에 이 경우는 pass한다.
			if (curTreasureNum > capacity) 
				continue;
			
            // 다음 섬에 보석이 있든 없든, 그냥 지나가는 경우
            // 만약, 현재 보석 소지 상황에 따른 다음 섬을 방문한 적이 없다면 방문한다. 
			if (visited[nxtIsland][curTreasures] == false)
			{
				visited[nxtIsland][curTreasures] = true;
				q.push({ nxtIsland, curTreasures });
			}
			
            // 만약 다음 섬에 보석이 있다면 보석을 가지고 간다.
            // 이 때, 보석 허용치 체크를 다시 안해도 되는데,
            // 왜냐하면 다리를 건넌 후, 다음 섬의 보석을 소지하기 때문에 다리를 건널 때는 보석 상황이 변하지 않기 때문이다.
			if (hasTreasure[nxtIsland] > -1)
			{
				int nxtTreasure = hasTreasure[nxtIsland];	// 디음 섬의 보석 번호

				int nxtTreasures = (curTreasures | (1 << nxtTreasure));	// 다음 섬의 보석을 소지하였을 때의 보석 소지 상황
				
                // 만약 다음 섬의 보석을 소지한 경우의 다음 섬을 방문한 적이 없다면 방문
				if (visited[nxtIsland][nxtTreasures] == false)
				{
					visited[nxtIsland][nxtTreasures] = true;
					q.push({ nxtIsland, nxtTreasures });
				}
			}
		}
	}
	
    // 가능한 모든 경우를 체크한 후, 최대 보석 개수를 return 한다.
	return maxTreasuure;
}

int main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	
    // 1번: 보물 초기화 (-1은 보석이 섬에 없다는 뜻)
	memset(hasTreasure, -1, sizeof(hasTreasure));
	
    // 2번: 입력
	cin >> islandNum >> bridgeNum >> treasureNum;
	
    // 보석의 번호는 0번부터 시작한다.
	for (int treasureIdx = 0; treasureIdx < treasureNum; ++treasureIdx) 
    {
		int treasureIsland;
		cin >> treasureIsland;
		
        // 입력 받은 섬에 각 보석의 번호를 저장한다.
		hasTreasure[treasureIsland] = treasureIdx;
	}
	
	for (int i = 0; i < bridgeNum; ++i) 
    {
		int island1, island2, capacity;
		cin >> island1 >> island2 >> capacity;

		// 다리는 양방향이므로 두 섬 모두에 대해 저장한다. 
		bridges[island1].push_back({ island2, capacity });
		bridges[island2].push_back({ island1, capacity });
	}

	int answer = Check();
	
	cout << answer << endl;

	return 0;
}