BOJ 20304 C++

풀이

xor연산을 이용하여 1을 비트마스킹해 옆으로 밀어서 현재의 숫자와 비트가 한자리만 차이나는 수를 구할 수 있다.
예를 들어 3이 있으면

1~20 자리까지 100만은 20자리로 표현가능
0011 //3
1부터 20자리까지 비교할거임
0001 //xor시 0010
0010 //0010
0100 // 0100
1000 // 1000

xor연산을 하면 위와 같이 현재수와 문제에서 제시하는 자리수 차이가 하나나는 수를 구할 수 있다.
이를 bfs를 활용하여 풀 수 있다.

코드

#include <iostream>
#include <queue>
#include <algorithm>

#define X first
#define Y second

using namespace std;
int dis[1000005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    int n; cin >> n;
    int m; cin >> m;
    queue<int> q;
    fill(dis, dis + n + 3, -1); 
    while(m--)
    {
        int tmp;
        cin >> tmp;
        q.push(tmp);
        dis[tmp] = 0;
    }
    int ans = 0;
    while(!q.empty())
    {
        int cur = q.front(); q.pop();
       
        for(int i = 0; i < 20; i++)
        {
            int next = cur ^ (1 << i);
            if(next > n || dis[next] >= 0)
                continue;
            //cout << cur << " goto " << next << " \n";
            q.push(next);
            dis[next] = dis[cur] + 1;
            ans = max(dis[next], ans);
        }
    }
    //cout << "arr: \n";
    for(int i = 0; i < 10; i++)
    {
        //cout << dis[i] << " ";
    }

}

주석을 풀고 보면 이해가 더 쉬울것이다.