[백준 시리즈] 13413번 : 실버 4 - 오셀로 재배치 / Python

제목 : 오셀로 재배

출처 : 백준 /  https://www.acmicpc.net/problem/13413

사용 알고리즘 : 그리디

---

문제 설명

초기 상태	목표 상태
○●●○○	○●○●○

1. 오셀로 말의 앞면은 흰색이고 뒷면은 검정색이다.

2. 말을 뒤집는 작업이나 두 말의 위치를 바꾸는 작업을 할 수 있다.

3. 초기 상태와 목표 상태가 주어졌을 때 목표 상태에 도달하는 최소 작업의 수를 구하라.

 

제한

시간 제한 : 2초

메모리 제한 : 256 MB

 

입력

테스트 케이스 수 T

오셀로 말의 개수 N (1<= N <= 100,000)

초기 상태 1줄

목표 상태 1줄

 

출력

입력받은 데이터에 대해 한 줄씩 결과 출력

---

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

N의 최대 크기가 100,000이므로 O(NlogN) 이하의 알고리즘이 요구된다.

 

2단계 : 하나의 케이스에 대해 답을 어떻게 구할 수 있는가?

케이스 1)

WWBB -> BBWB (답 : 2) 에 대해 답을 구해보자.

WWBB -> WBWB : 2번째와 3번째 말을 교환한다.

WBWB -> BBWB  : 1번째 말을 뒤집는다.

 

케이스 2)

 

BBBB -> BWBW (답 : 2) 에 대해 답을 구해보자. 2번째와 4번째 말을 뒤집으면 된다.

 

즉, 교환할 수 있는 말을 전부 교환한 후 뒤집는다.

 

횟수만 구하면 되므로 W상태의 틀린 말 개수와 B상태의 틀린 말 개수를 센 뒤, 짧은거+(긴거-짧은거)가 작업횟수이므로 max(W상태의 틀린 말, B상태의 틀린 말 개수)을 출력한다. 

 

3단계 : 2단계에서 사용한 방법을 일반화할 수 있는가?

일반화 할 수 있다. 2개의 말을 뒤집으면 2번의 작업이 필요하지만 두 말을 교환하면 1번의 작업만이 요구된다. 또한, 말을 교환하는데 아무 제약도 없기 때문에 먼저 교환 -> 뒤집기 순으로 작업하는 것이 항상 최소 횟수 작업임이 보장된다. 따라서, 이 문제는 그리디하게 해결할 수 있다.

---

정답 코드

t = int(input())
for _ in range(t):
    n = int(input())
    in1 = input()
    in2 = input()
    a, b = 0, 0

    for i in range(n):
        if in1[i] != in2[i]:
            if in1[i] == 'W':
                a += 1
            else:
                b += 1

    if a > b : a,b = b,a
    print(b)

 

* a가 항상 작은 수가 되도록 스왑 연산을 사용했다.

* python은 a, b = b, a로 스왑연산을 할 수 있다.