백준 13413) 오셀로 재배치

https://www.acmicpc.net/problem/13413

13413번: 오셀로 재배치

 

문제

로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다. 세희의 목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다. 아래의 예시를 참고하자.

초기 상태목표 상태

○●●○○

○●○●○

세희는 로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다.

1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.

위의 예시에서, 3번째와 4번째 말을 2번 작업을 통해 각각 뒤집으면 2번의 작업으로 목표 상태를 만들 수 있다. 하지만 1번 작업을 통해 3번째와 4번째 말을 골라 서로의 위치를 바꾸어주면 1번 만에 목표 상태에 도달할 수 있다. 초기 상태의 말과 목표 상태의 말이 주어질 때, 목표 상태에 도달할 수 있는 최소 횟수를 구하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 각 입력의 첫 번째 줄에는 오셀로 말의 개수 N(1≤N≤100,000)이 주어진다. 각 입력의 두 번째 줄과 세 번째 줄에는 각각 오셀로 말의 초기 상태와 목표 상태가 주어진다. 초기 상태와 목표 상태의 말의 개수는 항상 N과 일치한다. 흰색 면이 보이는 경우에는 W, 검은색 면이 보이는 경우에는 B로 주어진다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 한 줄에 1개씩 초기 상태에서 목표 상태를 만들기 위한 작업의 최소 횟수를 구한다.

예제 입력

3
5
WBBWW
WBWBW
7
BBBBBBB
BWBWBWB
4
WWBB
BBWB

예제 출력

1
3
2

 

---

 

이 문제를 풀 때 예제만 뚫어져라 쳐다보다가 자칫 조건을 하나 빠트릴 수 있다.

 

1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.

 

예제는 2개의 말을 고를 때, 서로 다른 말의 쌍이 붙어있기 때문에

아, arr[i] 와 arr[i+1]로 비교하면 되겠구나?

라는 생각에 빠져들 수 있다. 물론 나만 이렇게 생각했을수도^^..

 

 

일단 두 개의 string의 길이가 같으므로,

흰 면(W)과 검은 면(B)로 각각 구성된 위치가 있다면 변수에 1씩 더했다. (cnt++)

 

그리고 나서 str1[i] = W, str2[i] = B인 경우와 str1[i] = B, str2[i] = W 로 나눠서 각각의 조건에 충족하면 각각의 변수에 1씩 더했다. (wb++, bw++) 

 

이렇게 한 이유는 임의의 위치에서 서로의 말을 바꾸기 위한 조건을 충족시키기 위함이다.

 

 

 

간단히 예를 들어보겠다.

wbbw
bwbb

 

첫 번째 원소부터 각각의 문자열의 위치를 비교했을 때 서로 다른 경우의 수는 3가지다. (i=0, i=1, i=3) cnt = 3

 

다음으로 w -> b 순으로 된 경우의 수는 2가지이고, (i=0, i=3) wb = 2

 

b -> w 순으로 된 경우의 수는 1가지이다. (i=1) bw= 1

 

 

이 때 wb와 bw를 각각 1씩 감소시키면, 임의의 위치에서 2개의 말을 골라 위치를 바꾼 격이 되므로

전체 경우를 고려한 cnt에서 -1 해준다.

 

(cnt에 남아있는 경우의 수 : w-b, (b-w w-b) = 2개)

 

 

단, wb 또는 bw가 0이 된다면 더 이상 2개의 말을 고를 수가 없으므로, cnt에 남아있는 수가 바로 답이 된다.

 

 

 

전체 코드는 다음과 같다.

 

fun main() = with(System.`in`.bufferedReader()) {
    val bufferedWriter = System.out.bufferedWriter()
    repeat(readLine().toInt()) {
        val n = readLine().toInt()
        val str1 = readLine()
        val str2 = readLine()
        var cnt = 0
        var bw = 0
        var wb = 0
        for(i in 0 until n) {
            if(str1[i] != str2[i]) {
                if(str1[i]=='W' && str2[i]=='B') wb++
                else bw++
                cnt++
            }
        }
        while(bw != 0 && wb != 0) {
            bw--
            wb--
            cnt--
        }
        bufferedWriter.write("$cnt\n")
    }
    bufferedWriter.flush()
    bufferedWriter.close()
}