[백준] 2481 해밍 경로

문제 링크

http://icpc.me/2481

2481번: 해밍 경로

풀이

해밍 거리가 1인 경우는 비트 하나만 다른 것을 의미하기 때문에 비트가 하나만 다른 것들을 모두 그래프로 만든 후에 bfs를 돌리면 된다.

비트 하나만 바꿀 때는 XOR연산을 하면 된다. 그래프를 만들 때는 N개의 수에 k번 비트 연산을 하고 그 수가 존재하는지 map으로 확인하면 O(NKlogN)에 만들 수 있다.

cf) 입력을 int형으로 받아서 2시간 가까이 뇌절을 했다. 30자리 수니 매우 크다.. 조심하자..

코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define sz(x) int((x).size())

const int N = 1e5 + 5;
int arr[N], par[N], n, k; 
map<int, int> bit;
vector<int> v[N];

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        char inp[33]; scanf("%s", inp);
        int cal = 0, pw = 1;
        for (int i = k - 1; i >= 0; i--) {
            cal += (inp[i] - '0') * pw;
            pw <<= 1;
        }
        bit[cal] = i;
    }

    for (auto [num, idx] : bit) {
		for (int i = 0; i < k; i++) {
			if (bit.count(num ^ (1 << i))) {
                v[idx].push_back(bit[num ^ (1 << i)]);
            }
		}
	}

    queue<int> q;    
    q.push(1);
    par[1] = -1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto nxt : v[cur]) {
            if (par[nxt]) continue;
            q.push(nxt);
            par[nxt] = cur;
        }         
    }

    int m; scanf("%d", &m);
    while (m--) {
        int inp; scanf("%d", &inp);
        if (!par[inp]) {
            printf("-1\n");
            continue;
        }
        vector<int> ans;
        while (inp != -1) {
            ans.push_back(inp);
            inp = par[inp];
        }
        for (int i = sz(ans) - 1; i >= 0; i--) printf("%d ", ans[i]);
        printf("\n");
    }
}