백준 2418: 해밍 경로

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

 

이 문제는 한 눈에 보아도 너비 우선 탐색을 사용해야한다.

문제는 해밍 거리가 1인 이진수 코드를 그래프로 그리는 법이다.

반복문을 두 번 돌려서 그래프를 그리는 방법이 먼저 생각나지만, N이 100,000까지 올라가서 시간 초과가 날 것은 뻔하다.

 

그렇다면 1의 갯수로 각 이진수 코드를 분류한뒤, BFS를 돌 때 (현재의 이진수 코드의 1의 갯수 + i (-1 <= i <= 1, i는 정수))의 그룹을 둘러보는 것은 어떨까? 이전 방법보다 더 낫겠지만, 이 방식으로 문제를 통과 할 수 있을지는 의문이 든다.

예로 K가 최대 30일 때, 1의 갯수가 15개인 그룹은 ₃₀C₁₅ 가지의 가능성이 있는데, 이 갯수는 굉장히 많다. 그렇다면 다른 방식을 찾아야한다.

 

그렇게 떠오른 것이, HashMap을 사용하는 것이다. 먼저 Queue에 String을 넣고, BFS를 돌며, 현재 값을 한 번씩 변형시켜서, 해당 값이 입력에 없다면 넘어가고, 있다면, Queue에 넣는다. 단, 이미 방문한 값은 넣지 않는다.

입력에 있는지 없는지, 이미 방문한건지 아닌지를 확인하기 위해 HashMap을 사용했다.

입력이 최대 100,000, 문자열 길이 최대 30이라서 눈도장으로 보았을 때, 메모리 초과가 될 위험은 적을 것이다라 생각하여 다음과 같이 코드를 구현했다.

 

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

int N, K, M, J;
string S[100001];
unordered_map<string, int> um, v;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> K;
	for (int i = 1; i <= N; i++)
	{
		cin >> S[i];
		um.insert({S[i], i});
	}
	queue<int> q;
	q.push(1);
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		string str = S[now];
		for (int i = 0; i < K; i++)
		{
			str[i] = (str[i] == '1') ? '0' : '1';
			if (v.find(str) != v.end())
			{
				str[i] = (str[i] == '1') ? '0' : '1';
				continue;
			}
			auto iter = um.find(str);
			if (iter == um.end())
			{
				str[i] = (str[i] == '1') ? '0' : '1';
				continue;
			}
			v.insert({ str, now});
			q.push((*iter).second);
			str[i] = (str[i] == '1') ? '0' : '1';
		}
	}
	cin >> M;
	while (M--)
	{
		cin >> J;
		if (v.find(S[J]) == v.end())
		{
			cout << -1 << '\n';
			continue;
		}
		vector<int> ans;
		while (J != 1)
		{
			ans.push_back(J);
			J = v[S[J]];
		}
		ans.push_back(1);
		for (int i = ans.size() - 1; i >= 0; i--)
			cout << ans[i] << " ";
		cout << '\n';
	}
}

무사히 통과했다. 나는 편의상 문자열을 사용했지만, 이진수 코드가 int형 범위를 넘지않는 2³⁰이라서 비트마스크를 사용하면 더 효율적으로 코드를 구성할 수 있을 것이다.