[백준/BOJ] 13413. 오셀로 재배치 [Silver 4]

13413. 오셀로 재배치

문제출처 : https://www.acmicpc.net/problem/13413

일단 이 문제는 오셀로를 재배치하는 문제이지만, 사실상 위치는 그다지 중요하지 않다.
각각 BW의 개수와 위치가 틀린말의 갯수만 알면 풀수있다.
B->W또는 W->B로 바꾸는것은 1번의 작업횟수가 들어가고,
틀린말의 위치를 바꾸는것은 위치가 틀린말 2개를 1번의 작업횟수로 해결할수 있기 때문이다.

내가 쓰면서도 잘 이해가 안가는것 같은데,코드를 보면,

code

#include <stdio.h>
#include <stdlib.h> // 처음에 abs함수쓰려고 넣었는데 없어도 무방하다.
int main()
{
	char beginning[100000] = { 0 }, goal[100000] = { 0 };
	int i, j, T, N;
	int beginning_W = 0, goal_W = 0, wrong_arr = 0, not_match = 0, cnt = 0;
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &N);
		scanf("%s", beginning);
		scanf("%s", goal);
		for (j = 0; j < N; j++)
		{
			if (beginning[j] == 'W')
				beginning_W++;
			if (goal[j] == 'W')
				goal_W++;
			if (beginning[j] != goal[j])
				not_match++;
		}
		if (goal_W > beginning_W)
			wrong_arr = goal_W - beginning_W;
		else
			wrong_arr = beginning_W - goal_W;
		cnt = wrong_arr;
		not_match -= wrong_arr;
		cnt += (not_match / 2);
		printf("%d\n", cnt);
		beginning_W = 0, goal_W = 0, not_match = 0, wrong_arr = 0, cnt = 0;
	}
	return 0;
}

C언어라서 좀 복잡해 보이지만 찬찬히 보면 이해가 될것이다.

다시 깔끔하게 설명하자면,
결국에 우리가 구해야하는것은 로봇으로 할수있는 작업
배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
말 1개를 들어 뒤집어 놓아 색상을 변경한다.
을 이용해서 최소 작업횟수를 구하는 것인데,

처음구해야 하는것은 초기상태 배열과 목표배열을 비교해서
B와 W의 갯수
초기배열과 목표배열에 있는 말위치(틀린위치)의 횟수
를 구한다.
B와 W의 갯수를 구하는데 나는 B와 W중에 하나만 구해도 된다고 생각해서 W를 구했다.어차피 초기B,W와 목표B,W갯수의 차이를 구하는 것이 목표이므로 어떤 것을 구해도 관계없다.
초기B,W와 목표B,W갯수의 차이를 구했으면 keep해두고,
말위치가 다른 횟수를 구하고,
(말위치가 다른 횟수 - BW개수차이) 를 전체 작업횟수에 더해주면 로봇으로 할수있는 작업 2번에 해당하는 경우의 수를 모두 제거한게 된다.
그다음 로봇으로 할수있는 작업1번의 경우의수는 말위치가 다른 횟수2번이 1번위치를 바꿈으로서 해결되기때문에 (말위치가 다른 횟수/2)를 전체 작업횟수에 더해주면된다.

이게 말로설명하기가 좀 힘든부분이 없지않아 있는것같다ㅠㅠㅠ