[백준] 오셀로 재배치 : 13413번 - Python

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

13413번: 오셀로 재배치

 

 

 

문제 설명

 

-오셀로 말의 초기 상태와 목표 상태가 주어짐.

- 여기서 초기 상태와 목표 상태는 흰색 말과 검정색 말의 조합으로 이루어진 문자열임. (흰색 -> W, 검정색 -> B로 표현)

- 주어진 조건 2가지를 활용해서 초기 상태 -> 목표 상태에 도달할 수 있는 최소 횟수를 구해야 함.

* 최대한 바꾸는 횟수를 줄여서 초기 상태 = 목표 상태를 만들어야 하는 것이 관건!

 

 

 

내가 생각한 문제의 접근 방법

 

<문제의 조건>

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

- 초기 상태와 목표 상태의 검정색, 흰색 말의 개수가 같을 때와 다를 때로 나누어서 생각하기

 

1) 검정색, 흰색 말의 개수가 같을 때

: 조건 1 사용!

이미 제시된 문자열에 존재하는 검정색과 흰색 말들의 개수가 같으므로 말의 색상을 변경하는 조건 2보다는 위치를 바꿔서 목표 상태에 도달하도록 만들어 주는 것이 훨씬 더 효율적이다.

2) 검정색, 흰색 말의 개수가 다를 때

: 먼저 조건 2 사용 -> 조건 1 사용!

개수가 다를 때는 검정색 말과 흰색 말의 개수가 같아질 때까지 조건 2를 사용해서 색상을 변경해준다. 이 과정을 반복하다가 초기 상태와 목표 상태의 검정색, 흰색 말의 개수가 같아지면 1)번의 과정을 반복한다. (조건 1을 사용해서 색상을 변경하는 과정을 거침)

 

 

 

내가 막혔던 부분

 

시간 초과...

 

 

 

나의 문제 풀이 방법

T = int(input())

for _ in range(T):
    N = int(input())
    init = list(input())    # 초기상태(리스트로 저장)
    final = list(input())   # 목표상태
    
    cnt = 0
    cnt2 = 0

    if init.count('B') == final.count('B'): # init와 final의 검정색,흰색말의 개수가 같을 때
        for i in range(N):
            if init[i] != final[i]: # 만약 두 리스트의 i번째 값이 다르다면 바꿔야 하므로
                cnt += 1    # 바꾸는 횟수를 의미하는 변수 cnt에 1 더하기

        print(int(cnt/2))   # 두 요소를 바꾸는 횟수 2번 = 실제로 1번 바꿈 (나누기 2 해주기)

    else:   # init와 final의 검정색,흰색말의 개수가 다를 때
        for i in range(N):

            if init.count('B') != final.count('B'): # 다르다면
                if init[i] != final[i]: # 위와 달리 조건 2 먼저 사용!
                    final[i] = init[i]  # 두 값이 다르다면 final의 i번째 요소를 init의 i번째 요소 값으로 바꿔주기
                    cnt += 1  # 바꿨으니까 cnt에 1 더하기

            else:   # 위의 if문을 반복하다보면 검정색,흰색 말의 개수가 같아지는 순간이 옴.
                if init[i] != final[i]: # 조건 1 사용
                    cnt2 += 1   # 위에서 쓴 변수랑 겹치지 않게 cnt2에 1 더하기

        print(cnt + int(cnt2/2))    # 조건2를 통해 계산된 cnt와 조건 1을 사용해 계산된 (cnt2/2)를 더한 값 출력
                                    # 그게 최종 바꾼 횟수!!!

 

 

 

정답 소스코드 1

T = int(input())

for _ in range(T):
    N = int(input())    # 입력받을 말의 개수(길이)
    init = list(input())    # 초기상태
    final = list(input())   # 목표상태

    black = 0
    white = 0

    for i in range(N):
        if init[i] != final[i]: # 초기상태의 i번째 요소와 목표상태의 i번째 요소가 다를 때
            if final[i] == 'W': # 그 값이 W라면
                white += 1  # white 변수에 1 누적해서 더하기
            else:   # 그 값이 B라면
                black += 1  # black 변수에 1 누적해서 더하기
    
    print(max(white, black))    # 계산된 두 값 black,white중 더 큰 값을 출력

 

정답 소스코드 2

T = int(input())
for _ in range(T):
    N = int(input())
    init = list(input())
    final = list(input())

    cnt = 0
    cnt2 = 0

    for i in range(N):
        if init[i] != final[i]:
            if init[i] == 'W':
                cnt += 1
            else:
                cnt2 += 1

    print(cnt + cnt2 -min(cnt, cnt2))