백준(1080 행렬)

03 Jul 2020

문제

입력

---

문제 해설

이 문제는 3x3행렬 부분만 바꿔서 주어진 행렬이랑 같게 만드는 문제인데, 아이디어를 캐치하는게 중요해서 포스팅을 해본다. 일단 그냥 문제를 보면, 백트래킹이나 dfs/bfs는 터무니 없는걸 알 수 있다.
첫번째 아이디어 는 (0,0)행렬을 3x3으로 바꿔주면 다음번에는 이것을 바꿔줄 필요가 없다는 것이다. (0,0)을 맞추고, (0,1)을 맞추고, 계속해서 하나씩 바꾼다고 생각하면 된다. 3x3에 속아서 전체를 어떻게 바꿔서 어째저째 한다는 생각을 하면 머리가 터질것이다. 나또한 그랬다,,,
궁금할 것이다, 왜 (0,0) 부터일까? 자 그러면 (0,0)이 아니라 제일 좌측아래 좌표부터 시작을 한다면, 나중에 (0,0) 좌표 바꿔줄 때 아래것도 다 변해서 지금까지 세팅해준게 의미가 없어진다. 그림을 그리면서 생각해보면 쉽다. —–

N, M = list(map(int, input().split()))
#번환해야할 행렬
map_list = [list(map(int, list(input()))) for _ in range(N)]
#목표의 행렬
wanted_list = [list(map(int, list(input()))) for _ in range(N)]

#3x3부분을 다 바꿔주기 위한 함수
def changeAll(start_coord, arr):
    x, y = start_coord
    for i in range(x, x+3):
        for j in range(y, y+3):
            arr[i][j] = 1 - arr[i][j] 

cnt = 0 #횟수 세주는 변수
#행렬을 초과하지 않게 -2만큼 경계준다.
for i in range(0, N-2):
    for j in range(0, M-2):
        #좌표의 값이 같지 않다면
        if map_list[i][j] != wanted_list[i][j]:
            cnt += 1
            changeAll((i,j), map_list)
            
#flag = 0일 때는 변환했다는 것이고, 1일때는 변환해도 동치가 불가
flag = 0
for i in range(N):
    if map_list[i] != wanted_list[i]:
        print(-1)
        flag = 1
        break
if flag == 0:
    print(cnt)

다른 풀이를 보며 얻은건데, 굳이 for문을 돌려가면서 좌표를 일일히 받을 필요 없이

map_list = [list(map(int, list(input()))) for _ in range(N)]

이렇게 해주면, 더 빠르고 간편하게 정수형태로 리스트를 만들 수 있다.