[백준] 1080 행렬 (Python 파이썬)

문제 설명

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

0과 1로 이루어진 행렬 A 와 행렬 B가 주어질 때, 행렬 A를 행렬 B로 전환하는데 필요한 횟수를 구하는 문제이다.

이 때, 1회 전환하다는 것은 3x3의 행렬을 뒤집는 것이다.

예를 들어,

000                     111

010                     101

111  을 뒤집으면   000 이 된다.

---

풀이 과정

이 문제는 그리디 알고리즘으로 접근할 수 있다.

변환 전의 행렬을 A, 전환 후의 행렬을 B라고 하자.

현재 A 행렬의 내 위치에서 B 행렬과 일치하지 않는 부분이 있다면 그 부분부터 3x3 범위안의 행렬을 뒤집어주면 된다.

 

즉, 현재 내 위치만 보고 내 위치의 원소가 같은 위치에서의 B행렬과 일치하지 않는다면 뒤집는 것이기 때문에

그리디 알고리즘이라고 볼 수 있다.

n, m = map(int, input().split())
graph1 = []
graph2 = []
count = 0

def convertgraph(i, j):			# 3x3을 뒤집는 함수
    for x in range(i, i + 3):
        for y in range(j, j + 3):
            graph1[x][y] = 1 - graph1[x][y]


for i in range(n):				# 변환 전 함수 입력
    graph1.append(list(map(int, input())))

for i in range(n):				# 변환 후 함수 입력
    graph2.append(list(map(int, input())))

for i in range(n - 2):
    for j in range(m - 2):
        if graph1[i][j] != graph2[i][j]: # 일치하지 않는 부분 발생
            convertgraph(i, j)			 # 뒤집고
            count += 1				 	 # 횟수 + 1
flag = 0							# 변환 할 수 있는지 나타내는 변수

for i in range(n):					# 변환 후 일치하는지 확인
    for j in range(m):
        if graph1[i][j] != graph2[i][j]:
            flag = 1
            break

if flag == 1:							# 변환이 불가능 하면 -1 반환
    print(-1)
else:
    print(count)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !