[백준 1080] 행렬 해설 및 풀이 (파이썬)

백준 알고리즘 1080번 | 행렬 

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

---

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

 

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

 

출력

첫째 줄에 문제의 정답(뒤집을 수 있는 최소 횟수)을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

예제 입력 1

3 4
0000
0010
0000
1001
1011
1001

예제 출력 1

2

 

예제 입력 2

3 3
111
111
111
000
000
000

예제 출력 2

1

 

예제 입력 3

3 3
000
000
000
000
000
001

예제 출력 3

-1

---

해설

이 문제는 0과 1로 이루어져 있는 리스트가 주어집니다.

리스트를 뒤집을 수 있는데, 한번 뒤집을 때 단위의 3x3입니다.

최소한으로 뒤집어서 A를 B로 만들 수 있는 최소 뒤집기 횟수를 구합니다.

 

만약 뒤집어서 만들 수 없다면, -1을 출력합니다.

 

이 경우에는 A를 총 3번 뒤집으면 B로 만들 수 있습니다.

 

이런 느낌으로 진행

 

 

 

이 문제의 이해.

리스트 끝쪽에 있는 두 블럭은 개별 뒤집기가 불가.

기본 뒤집기 사이즈가 3x3이라서 그렇다.

뒤집기 사이즈가 3x3입니다.

뒤집기의 끝이 벽에 닿는 경우에는 뒤집을 수 없으니,

뒤집기 후에도 A와 B가 같지 않다면, 만들 수 없는 것입니다.

A를 B로 만들 수 없다.

 

N, M이 4, 4이라면

각 리스트의[0,1][0,1]의 수가 같은지만 보고 뒤집을지 판단하면 됩니다.

  이런식으로 인식 후, 뒤집기를 하면 됩니다.

 

이 문제의 예외

-1을 반환해야 할 때

(3x3 뒤집기로 만들 수 없는 경우)

 

 

1. 3x3보다 작으면서, 리스트A와 리스트B가 다른 경우:

# 리스트A, B가 다를 때
1 1
1
0

-1

# 리스트A, B가 같을 때
1 1
1
1

0

 

2. 뒤집어서 만들 수 없는 경우.

3 3
000
000
000
000
000
001

-1

 

 

파이썬 코드는 다음과 같습니다.

n, m = map(int, input().split()) 
listA = []
for _ in range(n): # 리스트A 선언
    listA.append(list(map(int, list(input()))))
listB = []
for _ in range(n): # 리스트B 선언
    listB.append(list(map(int, list(input()))))


def check(i, j): # 뒤집기 함수
    for x in range(i, i+3):
        for y in range(j, j+3):
            if listA[x][y] == 0:
                listA[x][y] = 1
            else:
                listA[x][y] = 0


cnt = 0 # 카운트
if (n < 3 or m < 3) and listA != listB:
    # 예외 1, 리스트가 작을 때
    cnt = -1
else:
    for r in range(n-2):
        for c in range(m-2):
            if listA[r][c] != listB[r][c]:
                cnt += 1
                check(r, c)

if cnt != -1:
    if listA != listB: # A와 B가 같은지 확인
        cnt = -1
print(cnt)

---

이번 문제는 티어에 비해 굉장히 어려웠어요. ㅜ

난이도 기여에서는 실버2 ~ 골드5 왔다갔다 하네용..