[백준][Python]1080번(행렬)

백준 1080번

✔️ 문제 풀이

◾ 뒤집기 문제의 특징

• 뒤집기 문제를 풀 때는 뒤집고 안 뒤집고만 고려해주면 된다
• 즉, 한 번 뒤집은 걸 또 뒤집는 순간 그 케이스는 중복이 된다!
  (A를 뒤집고, B를 뒤집었는데 A를 다시 뒤집으면 다른 결과가 나오지 않을까?를 걱정하지 않아도 된다)

◾ 그리디 알고리즘

• 처음에는 깊이 우선 탐색으로 코드를 작성하려 했으나 시간초과가 뜰 것이라고 판단해서 그리디 알고리즘으로 작성
• 질문 게시판을 보니 이 문제의 풀이가 왜 그리디 알고리즘인가?에 대한 질문이 많은데, 목적하는 값과 다른 값을 찾는 순간 그 케이스는 무조건 뒤집어야 하며, 한 번 뒤집은 부분행렬은 다시 뒤집지 않기 때문에 결국 뒤집을 것인가 말것인가를 결정하는 것 자체가 최적해를 찾는 과정이기 때문인 것 같다.

◾ check 함수

• matrix1을 돌면서 matrix2과 다른 일치하지 않는 원소의 좌표를 반환한다
• 일치한다면 좌표로 m, n을 반환한다
  (처음에는 두 행렬이 일치할 경우 False를 return할까? 를 고민했지만 어차피 m, n은 인덱스 값으로는 존재할 수 없고, 반환값의 형태는 일치시켜 주는 것이 낫다고 판단해서 이와 같이 작성하였다.)

◾ convert 함수

• 일치하지 않는 원소의 좌표를 맨 왼쪽, 맨 윗쪽으로 해서 3x3 크기의 부분행렬을 뒤집는다.
• convert 함수가 실행될 때마다 cnt 값을 1씩 증가시킨다.

◾ 이미 뒤집은 곳인지 확인

• check의 리턴값으로 뒤집힌 좌표의 원소는 뒤집힌 순간 matrix2의 값과 동일해진다.
• 즉, 자신을 기준으로 부분행렬이 뒤집혔다면 그 기준이 된 원소는 다음 check 탐색 때 절대 좌표로 다시 반환되는 일이 없다.
• px, py에 이전 x, y 값을 저장해주어 check 함수가 앞선 탐색과 같은 좌표를 return한다면 더 이상 뒤집을 수 있는 부분행렬이 남아있지 않은데 matrix1과 matrix2가 다르다는 뜻, 즉 원하는 결과를 도출할 수 없다는 뜻이므로 -1을 출력하고 탐색을 종료한다.
• check함수가 (m, n)을 return한다면 정답을 찾은것임으로 cnt를 출력하고 탐색을 종료한다.

◾ 방문 확인

• 처음에는 px, py를 이용해 이전 x, y값을 저장하지 않고 converted 배열을 선언해 방문 체크를 했는데, 시간 초과가 떴다...
• 인덱스를 활용한 배열의 원소 접근은 시간이 O(1)이라고 알고 있는데 왜인지 모르겠다.
• 심지어 최종 제출 코드에 converted 배열을 선언하고 값을 할당하는 부분까지 추가했는데도 시간초과가 안 뜬다.
• 모두 동일한 상태에서 if px==x and py==y를 if converted[y][x]로 변경하면 시간초과가 뜬다...

최종 제출 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
matrix1 = [list(map(int, input().strip())) for _ in range(n)]
matrix2 = [list(map(int, input().strip())) for _ in range(n)]

def check():
  for i in range(n):
    for j in range(m):
      if matrix1[i][j] != matrix2[i][j]:
        return (j, i)
  return (m, n)

def convert(x, y):
  for i in range(y, y+3):
    for j in range(x, x+3):
      if matrix1[i][j]: matrix1[i][j] = 0
      else: matrix1[i][j] = 1

cnt = 0
px, py = -1, -1

while True:
  x, y = check()
  if px==x and py==y:
    print(-1)
    break
    
  px,py = x,y
  
  if x==m and y==n:
    print(cnt)
    break
    
  if x <= m-3 and y <= n-3:
    convert(x, y)
    cnt += 1

✔️ 실행 결과