[2016 국민대 교내 경시대회] A. 오셀로 재배치
BOJ 13413 오셀로 재배치 (https://www.acmicpc.net/problem/13413)
앞면은 검정, 뒷면은 흰색으로 된 오셀로 말을
① 임의의 2개의 말을 위치를 바꾸거나(인접한 말일 필요없음)
② 말 1개를 뒤집어 색깔 변경
하는 작업 중 하나를 골라 시행할 수 있을 때, 초기 상태에서 목표 상태까지 도달할 수 있는 최소 작업 횟수를 구하는 문제입니다.
특정한 알고리즘을 사용하는 문제는 아니지만, 예시들을 통해 어떻게 말을 바꿔나가는 것이 최소 작업 횟수가 되는지를 생각하다 보면 방법을 알 수 있습니다.
제가 사용한 방법은
B여야 하는데 W인 말과, W여야 하는데 B인 말을 서로 모두 바꾼 후에(①) 아직 목표 상태에 도달하지 못한 말들을 각각 뒤집는(②) 방법입니다. 검정색에서 흰색이 돼야 하는 말의 갯수를 n(B->W), 흰색에서 검정색이 돼야 하는 말의 갯수를 n(W->B) 라고 한다면, ①, ② 각각 작업 횟수는
① min( n(B->W), n(W->B) )
② abs( n(B->W) - n(W->B) )
가 됩니다.
위의 상황을 그림으로 나타내면 다음과 같습니다.
그런데, n(B->W)가 n(W->B)보다 큰 경우에 ① = n(W->B), ② = n(B->W) - n(W->B)가 되어 ① + ②가 n(B->W)가 된다는 것을 계산을 통해 확인할 수 있습니다. 반대의 경우(n(W->B)가 n(B->W)보다 큰 경우)에 대해서도 계산해 보면, ① + ②가 n(B->W)와 n(W->B)의 값 중 큰 값이 이 된다는 것을 확인할 수 있습니다.
따라서, ① + ②의 결과는 항상
max( n(B->W), n(W->B) )
가 된다는 것을 알 수 있습니다.