BOJ 27909 - Diskurs
교육적인 문제이다.
BOJ 28032 - Field Day와 동일하게 풀 수 있다.
$a_i$에서 가장 많이 비트가 다른 $a_j$를 찾는 문제는 $b_i=a_i \oplus (2^m - 1)$ 라 할 때,
$b_i$ 들의 거리를 $0$으로 초기화한다음 최단거리를 구하고
$a_i$ 의 최단거리를 $m$ 에서 빼는 문제로 환원된다.
Solution 1 - 최단거리 갱신
최단거리를 업데이트하는 방법은 비트마스킹이기 때문에 최적화를 해줄 수 있는데,
마치 플로이드 와샬처럼 진행하는 것이다.
$i ~ (0 \le i < m)$ 번 째 비트를 순회하며 모든 $x ~ (0 \le x < 2^m)$ 에 대해
$$
D(x \oplus 2^i)=\text{Min}(D(x \oplus 2^i),\,D(x)+1)
$$
을 순회해주는 것으로 시간복잡도 $O(2^m \cdot m)$ 에 구해줄 수 있다.
이 방법이 올바른 결과를 내는 이유는 다음과 같다.
- $D(x)$ 에 대해 그것의 실제 값보다 더 줄어들 수 없다.
- $D(x)$에서 $D(y)$로의 거리가 $k$라면, 알고리즘이 종료되고 $D(y) \le k$이다.
$x$를 순회하며 $D(x)$를 갱신해주는 것이 아닌 이유는 올바른 순서로 최단경로가 갱신되게하기 위함이다.
Solution 2 - Multi Source BFS
가장 생각하기 쉬운 방법일 것이고, $b_i$ 들에 대해서 거리를 $0$으로 주고 Multi Source BFS를 돌리고 간선은 비트가 하나씩 다른 수들로 가는 것으로 쳐서 최단거리를 찾아주는 것이다.
Comments