해밍 경로 2 (JUNGOL 5686)

 

https://jungol.co.kr/problem/5686?cursor=MTMsMSw1

---

아이디어

0이상 2_M미만의 수를 정점으로 하는 그래프를 생각해봅시다. 이때 i와 j를 잇는 간선이 있다는것은 i와 j사이의 해밍 거리가 1이라는것을 의미합니다. 그러면 등장하는 모든 x에 대하여 가장 멀리 떨어진 점을 찾아주면 됩니다. 이는 2_M-1 xor x와 가장 가까운 거리에 있는 점을 의미하므로, 모든 x에 대하여 2_M-1 xor x들을 잡고, 이것들을 기준으로 멀티소스 BFS를 사용해주면 각 점마다 가장 가까운 점까지의 거리를 구할 수 있습니다.

---

소스코드

#include <iostream>
#include <queue>
#define ll long long
using namespace std;

bool visit[1050101]={0};
int dis[1050101]={0};
int arr[1050101]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,M,i;
    queue <ll> q;

    cin>>N>>M;
    for (i=0;i<N;i++)
    {
        cin>>arr[i];
        q.push(arr[i]);
        visit[arr[i]]=true;
    }

    while (q.size())
    {
        ll now=q.front();
        q.pop();

        for (i=0;i<M;i++)
        {
            ll next=now^(1<<i);
            if (visit[next]) continue;
            visit[next]=true;
            dis[next]=dis[now]+1;
            q.push(next);
        }
    }

    for (i=0;i<N;i++)
        cout<<M-dis[((1<<M)-1)^arr[i]]<<' ';
}