[백준/BOJ] 백준 2001번 : 보석 줍기

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

2001번: 보석 줍기

visited[1 << 14][101]에 [보석 획득 상황(비트로 표현)][위치]일 때 방문했는지를 체크하여 탐색을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
using namespace std;

int n, m, k;
vector<pair<int, int>> adj[101];
vector<int> gold_check(101, -1);
int visited[1 << 14][101]; //[보석 획득 상황][위치]
int result = 0;

void Pre()
{
	for (int i = 0; i < (1 << 14); i++)
		for (int j = 0; j < 101; j++)
			visited[i][j] = 0;
}

void Solve(int gold_status, int gold_num, int here)
{
	visited[gold_status][here] = 1;

	//시작지점일때
	if (here == 1)
		result = max(result, gold_num);

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i].second;
		int gold_limit = adj[here][i].first;

		//there지점으로 갈 수 있을때
		if (gold_limit >= gold_num)
		{
			//there지점이 보석이 있는 위치일때
			if (gold_check[there] != -1)
			{
				int there_gold = gold_check[there];

				//there지점 보석이 이미 있을때
				if ((gold_status & (1 << there_gold)) != 0)
				{
					if (visited[gold_status][there] == 0)
					{
						Solve(gold_status, gold_num, there);
					}

				}

				else
				{
					//there지점에서 보석을 주울때
					if (visited[gold_status | (1 << there_gold)][there] == 0)
					{
						Solve(gold_status | (1 << there_gold), gold_num + 1, there);
					}

					//there지점에서 보석을 줍지 않을때
					if (visited[gold_status][there] == 0)
					{
						Solve(gold_status, gold_num, there);
					}

				}
			}

			else
			{
				if (visited[gold_status][there] == 0)
				{
					Solve(gold_status, gold_num, there);
				}
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n >> m >> k;

	for (int i = 0; i < k; i++)
	{
		int input;
		cin >> input;

		gold_check[input] = i;
	}

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back(make_pair(c, b));
		adj[b].push_back(make_pair(c, a));
	}
	adj[1].push_back(make_pair(100, 1));
	Solve(0, 0, 1);

	cout << result;

	return 0;
}