[BOJ 1080, Python 3] 행렬

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

1080번: 행렬

 

풀이

어느쪽 모서리이든 (0, 0), (0, m-1), (n-1, 0), (n-1, m-1) 어느쪽으로 출발해도 상관은 없는데 가장 대중적인 (0, 0)을 기준으로 말하겠습니다.

 

먼저 정답부터 말하고 풀이를 설명드리겠습니다.

처음 행렬을 s, 정답 행렬을 answer라고 가정합시다.

문제에서 3by3행렬을 뒤집는다고 합니다. 그러면 n - 2개의 행과 m - 2개의 열을 확인하여 s[i][j]의 값이 anwer[i][j]의 값과 다르면 (i, j) ~ (i+2, j+2)까지 3by3 행렬을 뒤집고 ,아니면 넘어간 뒤에 마지막에 s와 answer이 같은 값인지 확인해주고 답을 출력해주면 됩니다.

 

이게 왜 가능하냐면 먼저 행렬의 값은 0 아니면 1만 가능하기 때문에 두 번 이상 뒤집는 것은 의미가 없습니다.

그래서 가만히 놔두는 방법과 한 번 뒤집는 방법만 가능합니다.

만약 입력값이 3 by 3 행렬이 들어왔다고 가정해봅시다. 그러면 (0, 0)을 확인하여 s[0][0] = answer[0][0]이라고 해봅시다. 뒤집을 필요가 없으니 지나가겠죠? 그러면 이제 s[0][0]값은 다시는 건들 수 없는 고정된 값이 됐습니다.

계속 확인하다가 (2, 2)까지 왔는데 s[2][2]는 행렬을 뒤집어야 한다고 합니다. 그런데 3 by 3 행렬에서는 (2, 2) 값을 건든다면 (0, 0)값을 뒤집어야해서 answer배열을 만들 수 없게 됩니다.

이렇게 s[0][0]같이 고정되버린 값을 뒤집는다면 그건 더 이상 답이 될 수 없는 것에서 출발하는 아이디어 입니다. 아직 확정되지 않은 값은 언제든지 뒤집어도 상관 없는 것이죠

 

이걸 크기를 더 확장해보면 n - 2 by m - 2 행렬 값을 고정할 수 있게 됩니다.

4 by 8 행렬이 있다고 해봅시다.

 

(0, 0)에서 출발하여 2중 for문을 사용해 (4 - 2) by (8 - 2) 행렬까지는 값을 고정할 수 있습니다.

이제 여기서 흰색 칸 값 하나를 바꿔야 하는게 정답이면 최소한 빨간색 한 칸은 뒤집어야해서 정답이 무조건 될 수가 없습니다.

그래서 이렇게 n - 2 by m - 2 행렬만 확인해도 정답인지 아닌지 확인할 수 있게 됩니다.

 

 

 

코드

N < 3 , M < 3인 경우에는 행렬을 뒤집을 수 없으니 처음 행렬이 정답 행렬과 같으면 0, 아니면 -1을 출력하도록 했습니다.

def check():
    flag = True
    for i in range(n):
        for j in range(m):
            if s[i][j] != answer[i][j]:
                flag = False
    return flag
 
n, m = map(int, input().split())
s = [[*input()] for _ in range(n)]
answer = [[*input()] for _ in range(n)]
if n < 3 and m < 3:
    print([-1, 0][check()])
    exit()
 
ans = 0
for i in range(n - 2):
    for j in range(m - 2):
        if s[i][j] != answer[i][j]:
            ans += 1
            for x in range(i, i+3):
                for y in range(j, j+3):
                    s[x][y] = '1' if s[x][y] == '0' else '0'
 
print([-1, ans][check()])