13413-백준-오셀로 재배치

1. 문제 출처

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

13413번: 오셀로 재배치

2. 풀이

그리드 알고리즘 문제로  뒤집어야 하는 돌의 위치를 먼저 파악 후 자리를 바꾸는 돌을 파악한다.

# 그리디 알고리즘을 사용하여 먼저 색깔의 차이를 확인한 후
# 자리를 바꾸도록 한다.


#입력
t = int(input())

for _ in range(t):
    size = int(input())
    init = input()
    goal = input()
    result = 0 
    change_count = 0
    # 횐색돌의 차이만큼 뒤집어야 하기 때문에 결과 값에 차를 더해준다.
    result += abs(init.count("W")-goal.count("W"))
    # 그 후 각각의 문자열에서  서로 다른 것을 구해준다.
    for idx in range(size):
        if init[idx] != goal[idx]:
            change_count+=1
    # 그 값이 result 보다 크다면 뒤집어주어야 하는 result 값을 제외한
    # 나머지 값은 서로 자리를 바꿔주어야 하는 돌이므로 무조건 짝수개가 존재하고
    # change_count - result 에 2를 나눠줌으로서 자리를 바꿔야하는  돌의 개수를 구한다.
    if change_count > result:
        result += int((change_count-result)/2)
    print(result)