[백준/BOJ] 백준 18235번 : 지금 만나러 갑니다

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

18235번: 지금 만나러 갑니다

discovered[500001][2][20]; //[위치][오리:0, 육리:1][몇일차인지] = 방문여부 를 이용하여 너비 우선 탐색을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;

int n, a, b;
int discovered[500001][2][20]; //[위치][오리:0, 육리:1][몇일차인지] = 방문여부
queue<tuple<int, int, int>> q; //(위치, 오리인지 육리인지(오리:0, 육리:1), 몇일차인지)

void Pre()
{
	for (int i = 0; i < 500001; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 20; k++)
				discovered[i][j][k] = 0;
}

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

	Pre();

	cin >> n >> a >> b;

	discovered[a][0][0] = 1;
	discovered[b][1][0] = 1;
	q.push(make_tuple(a, 0, 0));
	q.push(make_tuple(b, 1, 0));

	int result = -1;
	while (!q.empty())
	{
		int here = get<0>(q.front());
		int a_b = get<1>(q.front());
		int here_depth = get<2>(q.front());
		q.pop();

		if (discovered[here][0][here_depth] == 1 && discovered[here][1][here_depth] == 1)
		{
			result = here_depth;
			break;
		}

		int there1 = here + pow(2, here_depth);
		int there2 = here - pow(2, here_depth);
		int there_depth = here_depth + 1;

		if (there1 >= 1 && there1 <= n)
		{
			discovered[there1][a_b][there_depth] = 1;
			q.push(make_tuple(there1, a_b, there_depth));
		}

		if (there2 >= 1 && there2 <= n)
		{
			discovered[there2][a_b][there_depth] = 1;
			q.push(make_tuple(there2, a_b, there_depth));
		}
	}

	cout << result;

	return 0;
}