백준 이진수 게임(18112)

이진수 게임

1. 힌트

1) 이진수의 길이는 최대 $10$입니다. $2^{10} = 1024$이므로 이를 정점으로 생각해서 그래프 탐색 알고리즘을 적용할 수 있습니다.

2) 비트마스킹과 xor을 이용하면 정점간의 이동을 쉽게 구현할 수 있습니다.

2. 접근

힌트 참조

3. 구현

public class Main {
	
	static int bfs(int u, int v) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(u);
		int[] dist = new int[1024];
		Arrays.fill(dist, -1);
		dist[u] = 0;
		while (!q.isEmpty()) {
			int here = q.poll();
			int range = 9;
			while (range - 1 >= 0 && (here & (1 << range)) == 0) range--;
			for (int i = 0; i < range; i++) {
				int there = here ^ (1 << i);
				if (dist[there] == -1) {
					q.offer(there);
					dist[there] = dist[here] + 1;
				}
			}
			if (here + 1 < 1024 && dist[here + 1] == -1) {
				q.offer(here + 1);
				dist[here + 1] = dist[here] + 1;
			}
			if (here - 1 >= 0 && dist[here - 1] == -1) {
				q.offer(here - 1);
				dist[here - 1] = dist[here] + 1;
			}
		}
		return dist[v];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int L = Integer.parseInt(br.readLine(), 2);
		int K = Integer.parseInt(br.readLine(), 2);
		System.out.println(bfs(L, K));
	}

}