[백준 1080번] 행렬 - 파이썬

 

문제 링크:

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

1080번: 행렬

 

---

풀이 과정:

이 문제는 행렬 A를 행렬 B로 변환할 때 필요한 최소 횟수를 구하는 문제이다.

행렬 변환이 불가능하다면 -1을 출력한다.

단, 행렬의 원소를 하나라도 바꾸려고 할 때 그 원소를 포함한 3x3 부분 행렬이 전부 교체된다.

문제에 있는 것처럼 1은 0으로, 0은 1으로 교체가 된다.

 A      B
0001 1110
1110 0011
0100 1100

예를 들어 다음과 같이 A, B 행렬이 있다고 하자.

A -> B로 바꾸려고 할 때, A의 1행, 1열인 0 값을 1로 바꿔야 한다. (B의 1행, 1열 값이 1이기 때문)

 

이때 다음과 같이 굵게 색칠한 부분(3x3 행렬)이 변환이 되고, 계산 횟수가 1이 추가된다. 

0은 1로, 1은 0으로 변환된다.

 A               A
0001           1110
1110      ->  0000
0100           1010

 

이 점을 참고하여 순서대로 문제를 해결해보자.

★ 1.  3x3 부분행렬을 바꾸는 함수 만들기 (def 이용)

2. 차례대로 행렬의 원소를 받아 정답 행렬로 바꾸어보고, 이에 따른 계산 횟수 계산하기

3. 행렬을 바꿀 수 없으면 -1, 행렬을 바꿨으면 계산횟수 출력

 

풀이 코드:

# 1080번 행렬

n, m = map(int, input().split())
count = 0
non_answer = 0

# 변환할 행렬과 정답 행렬 입력받기
change_matrix = [list(map(int, input())) for _ in range(n)]
answer_matrix = [list(map(int, input())) for _ in range(n)]

# 3x3 행렬 변환 함수 생성
def convert_matrix(i, j, arr):
  for x in range(i, i+3):
    for y in range(j, j+3):
      arr[x][y] = 1 - arr[x][y]

# 차례대로 원소를 받아
for i in range(n-2):
  for j in range(m-2):
    # 변환할 행렬의 원소가 정답 행렬과 불일치시 3x3 행렬 값변환
    if change_matrix[i][j] != answer_matrix[i][j]:
      convert_matrix(i, j, change_matrix)
      count += 1

# 변환할 행렬과 정답 행렬 비교 검증
for i in range(n):
  for j in range(m):
    # 불일치시 -1을 출력
    if change_matrix[i][j] != answer_matrix[i][j]:
      non_answer = -1

# 정답 출력
if non_answer == -1:
  print(-1)
else:
  print(count)

 

 

백준 1080번 행렬