백준 - 2479번 : 경로 찾기 (C++)

풀이 방법 : DFS

습관적으로 DFS로 풀긴 했지만 아무래도 최단경로를 구해야하는 문제다보니 BFS로 푸는게 더 빠를 것 같다.

그냥 출발 코드에서 시작해서 길이가 해밍 거리가 1인 거리를 찾아가면서 탐색해가면 된다. 이는 비트셋으로 입력을 받으면 xor연산자를 이용하면 편하게 구할 수 있다.

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

vector<bitset<30>> vecCode;
bool Check[1001] = {};
int N, K;
int Src, Dest;
bool Enable = false;

vector<int> vecAnswer;

void DFS(int Current, vector<int> vecIdx)
{
	for (int i = 1; i <= N; ++i)
	{
		if (Check[i])
			continue;

		bitset<30> CurrentCode = vecCode[Current];
		bitset<30> NextCode = vecCode[i];
		
		if ((CurrentCode ^ NextCode).count() == 1)
		{
			vector<int> vecNext = vecIdx;
			vecNext.push_back(i);

			if (i != Src)
			{
				Check[i] = true;

				if (Enable && vecAnswer.size() <= vecNext.size())
				{
					return;
				}

				DFS(i, vecNext);
			}

			else
			{
				if (!Enable)
				{
					Enable = true;
					vecAnswer = vecNext;
				}

				else
				{
					int PrevSize = vecAnswer.size();
					int CurrentSize = vecNext.size();

					if (PrevSize > CurrentSize)
					{
						vecAnswer = vecNext;
					}

				}

				return;
			}
		}
	}
}

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

	cin >> N >> K;

	vecCode.resize(N + 1);

	for (int i = 1; i <= N; ++i)
	{
		cin >> vecCode[i];
	}

	cin >> Src >> Dest;

	vector<int> vecStart;
	vecStart.push_back(Dest);

	DFS(Dest, vecStart);

	if (!Enable)
	{
		cout << -1;
	}

	else
	{
		int Size = vecAnswer.size();

		for (int i = Size - 1; i >= 0; --i)
		{
			cout << vecAnswer[i] << ' ';
		}
	}

}