BOJ 2481 - 해밍 경로

BOJ 2479 - 경로찾기 문제를 먼처 푸는 것을 추천합니다.

======================================================

해밍 경로에서 차이가 1인 것끼리 경로가 될 수 있다는 것은 문제에 나와있다. 즉, 그래프 상의 A,B 해밍코드가 연결되기 위해서는 A^B 결과의 1인 비트가 반드시 한 개여야 한다는 것이다. 그래프를 구성한 뒤, 해밍 코드 1번부터 시작하는 BFS를 구성하여 trace할 배열을 따로 설정하여 저장해주기만 하면 된다.

문제는 간선을 잇기 위한 작업인데, 가능한 서로다른 A,B 쌍에 대해 간선을 알아보기 위한 시간복잡도는 O(N^2 K)다. K를 없애고 일반 정수로 한다고 하더라도 (A^B 결과의 log2하는 등), O(N^2)라서 시간이 초과된다. 따라서 다른 방법 중 하나가 해밍 거리가 1인 점을 이용하는 것이다.

반대로 N개의 해밍코드에 대해서 각각 하나의 코드를 골라서 비트를 하나를 바꿔준다. 예를 들자면, K=3, 해밍 코드가 100일때, N개의 해밍코드 내에 000이 있는지, 110이 있는지, 101이 있는지 판단을 하는 것이다. 따라서 찾는 것을 이분탐색으로 찾는다면 시간 내에 찾을 수 있게 된다. 따라서 시간복잡도는 O(K*N*lgN).

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
int main() {
	int N, K, i, j, k, diff,A,B,prev[100001],pos,stk[100001],M,d[100001],adjoin;
	char s[31];
	map<int, int> hash_a;
	scanf("%d%d", &N, &K);
	vector<vector<int>> adj(N+1);
	for (i = 1; i <= N; i++) {
		scanf("%s", s);
		d[i] = 0;
		for (j = 0; j < K; j++) {
			d[i] <<= 1;
			d[i] |= (s[j] - '0');
		}
		hash_a[d[i]] = i;
	}
	for (i = 1; i <= N; i++) {
		for (j = 0; j < K; j++) {
			adjoin = d[i] ^ (1 << j);
			auto it = hash_a.find(adjoin);
			if (it != hash_a.end())
				adj[i].push_back(it->second);
		}
	}
	memset(prev, -1, sizeof(prev));
	scanf("%d",&M);
	A = 1;
	queue<int> q;
	prev[A] = 0;
	q.push(A);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for(int v : adj[u])
			if (prev[v] == -1) {
				prev[v] = u;
				q.push(v);
			}
	}
	while (M--) {
		scanf("%d", &B);
		if (prev[B] == -1) printf("-1\n");
		else {
			pos = 0;
			for (i = B; i != A; i = prev[i])
				stk[pos++] = i;
			printf("%d ", A);
			while (pos--) printf("%d ", stk[pos]);
			printf("\n");
		}
	}
	return 0;
}