[백준/BOJ] 백준 20304번 : 비밀번호 제작

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

20304번: 비밀번호 제작

로그인 시도에 사용된 비밀번호 값들 에서 bfs를 통해 탐색을 하여 가장 깊은 depth를 구하는 방법으로 문제를 해결했다.

 

코드

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

int n;
int max_bit_size = 0; //비밀번호 최댓값의 비트 자리값 저장
int m;
vector<int> p;

queue<int> q;
vector<int> discovered(1000001, 0);
vector<int> depth(1000001, 0);

void Make_max_bit_size()
{
	int check = n;

	while (1)
	{
		if (check / 2 != 0)
		{
			max_bit_size++;
			check /= 2;
		}

		else
		{
			max_bit_size++;
			break;
		}
	}
}

int Solve()
{
	for (int i = 0; i < p.size(); i++)
	{
		q.push(p[i]);
		discovered[p[i]] = 1;
		depth[p[i]] = 0;
	}

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		for (int i = 0; i < max_bit_size; i++)
		{
			int there = (here ^ (1 << i));

			if (there <= n && discovered[there] == 0)
			{
				discovered[there] = 1;
				depth[there] = depth[here] + 1;
				q.push(there);
			}
		}
	}

	int ret = -1;
	for (int i = 0; i <= n; i++)
		ret = max(ret, depth[i]);

	return ret;
}

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

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int pi;
		cin >> pi;

		p.push_back(pi);
	}

	Make_max_bit_size();

	cout << Solve();

	return 0;
}