문제

한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다. 모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다. 동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다.

예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다. 그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다. 초기 상태에서 2행과 4행의 돌들을 뒤집으면, 두 번째 그림이 됩니다. 그 후, 2열, 4열, 5열의 돌들을 순서대로 뒤집는 다면, 총 5번의 동전 뒤집기를 통해 목표 상태가 되며, 이 경우가 최소인 경우입니다.

직사각형 모양의 공간에 놓인 동전들의 초기 상태를 나타내는 2차원 정수 배열 beginning, 목표 상태를 나타내는 target이 주어졌을 때, 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하는 solution 함수를 완성하세요. 단, 목표 상태를 만들지 못하는 경우에는 -1을 return 합니다.

제한사항

• 1 ≤ beginning의 길이 = target의 길이 ≤ 10
• 1 ≤ beginning[i]의 길이 = target[i]의 길이 ≤ 10
  • beginning[i][j]와 target[i][j]는 i + 1행 j + 1열의 동전의 상태를 나타내며, 0 또는 1의 값으로 주어집니다.
  • 0은 동전의 앞면을, 1은 동전의 뒷면을 의미합니다.

풀이

아이디어

• 우리는 동전을 뒤집는 횟수의 '최솟값'을 구하는 것 => 따라서, 똑같은 행이나 열을 뒤집는 건 고려하지 않는다. 괜히 복잡하게 생각하지 말자.
• 0과 1로 일일이 판단하지 말고, beginning과 target이 서로 다르다면 False로, 같다면 True로 치환한 보드판을 만들어서 그걸 가지고 진행한다.
• 동전 하나를 바꾸면 그 동전이 포함된 줄(행 또는 열)이 모두 바뀌기 때문에, 바깥쪽 행이나 열만 초반에 체크해주면 된다. (0행이나 0열)
  • 굳이 안쪽 칸까지 뭘 검사해줄 필요가 없다는 말이다.
• 그러면 target으로 가까이 가는 방법을 살펴보면 다음 4가지 방법이 있다.
  1. 행의 첫번째 칸이 False인 행들을 모두 뒤집어준다. 그 후 열의 첫번째 칸이 False인 열들을 모두 뒤집어준다.
  2. 행의 첫번째 칸이 True인 행들을 모두 뒤집어준다. 그 후 열의 첫번째 칸이 False인 열들을 모두 뒤집어준다.
  3. 열의 첫번째 칸이 False인 열들을 모두 뒤집어준다. 그 후 행의 첫번째 칸이 False인 행들을 모두 뒤집어준다.
  4. 열의 첫번째 칸이 True인 열들을 모두 뒤집어준다. 그 후 행의 첫번째 칸이 False인 행들을 모두 뒤집어준다.
• 이렇게 했을 때 answer를 업데이트시키고, 만약 answer이 업데이트 되지 않았다면 -1을 리턴하면 된다.

코드

```#M행 N열
def solution(beginning, target):
    M, N = len(beginning), len(beginning[0])
    tf_board1, tf_board2 = [[False] * N for _ in range(M)], [[False] * N for _ in range(M)]
    tf_board3, tf_board4 = [[False] * N for _ in range(M)], [[False] * N for _ in range(M)]
    
    #tf_board 올바른 값으로 채우기
    for i in range(M):
        for j in range(N):
            if beginning[i][j] == target[i][j]:
                tf_board1[i][j] = True
                tf_board2[i][j] = True
                tf_board3[i][j] = True
                tf_board4[i][j] = True
    
    answer = 3000
    #행 먼저, 열 나중
    temp1 = 0
    for i in range(M):
        if tf_board1[i][0] == True:
            temp1 += 1
            for j in range(N):
                tf_board1[i][j] = not tf_board1[i][j]
    for j in range(N):
        if tf_board1[0][j] == False:
            temp1 += 1
            for i in range(M):
                tf_board1[i][j] = not tf_board1[i][j]
    flag1 = True
    for i in range(M):
        for j in range(N):
            if tf_board1[i][j] == False:
                flag1 = False
                break
        if flag1 == False:
            break
    if flag1 == True:
        answer = min(answer, temp1)
    
    #열 먼저, 행 나중
    temp2 = 0
    for j in range(N):
        if tf_board2[0][j] == True:
            temp2 += 1
            for i in range(M):
                tf_board2[i][j] = not tf_board2[i][j]
    for i in range(M):
        if tf_board2[i][0] == False:
            temp2 += 1
            for j in range(N):
                tf_board2[i][j] = not tf_board2[i][j]
    flag2 = True
    for i in range(M):
        for j in range(N):
            if tf_board2[i][j] == False:
                flag2 = False
                break
        if flag2 == False:
            break
    if flag2 == True:
        answer = min(answer, temp2)
    
    #행 먼저, 열 나중(첫번째가 False일 때)
    temp3 = 0
    for i in range(M):
        if tf_board3[i][0] == False:
            temp3 += 1
            for j in range(N):
                tf_board3[i][j] = not tf_board3[i][j]
    for j in range(N):
        if tf_board3[0][j] == False:
            temp3 += 1
            for i in range(M):
                tf_board3[i][j] = not tf_board3[i][j]
    flag3 = True
    for i in range(M):
        for j in range(N):
            if tf_board3[i][j] == False:
                flag3 = False
                break
        if flag3 == False:
            break
    if flag3 == True:
        answer = min(answer, temp3)
    
    #열 먼저(False인것), 행 나중에
    temp4 = 0
    for j in range(N):
        if tf_board4[0][j] == False:
            temp4 += 1
            for i in range(M):
                tf_board4[i][j] = not tf_board4[i][j]
    for i in range(M):
        if tf_board4[i][0] == False:
            temp4 += 1
            for j in range(N):
                tf_board4[i][j] = not tf_board4[i][j]
    flag4 = True
    for i in range(M):
        for j in range(N):
            if tf_board4[i][j] == False:
                flag4 = False
                break
        if flag4 == False:
            break
    if flag4 == True:
        answer = min(answer, temp4)
    
    if answer == 3000:
        answer = -1
    
    return answer