[백준 1080] 행렬 Python

행렬

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 그리디 알고리즘

 

문제

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

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

입력

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

 

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

예제 입출력

 

반응형

---

Algorithm

구현 - Simulation
1. 다른 숫자인 곳을 왼쪽 위 지점으로 잡고 연산
2. 모두 변환 후 A와 B가 동일한지 비교

 

Code

# [x][y]의 위치의 값이 같은지 다른지 확인
def is_same(x, y):
    if A[x][y] != B[x][y]:
        return False
    else:
        return True

# [x][y]의 위치의 값을 변경
def change(x, y):
    # [x][y]부터 3x3이 범위를 벗어나면 for문 들어가지 않음
    if x+3 > N or y+3 > M:
        return False
    
    for xx in range(x, x+3):
        for yy in range(y, y+3):
            # 0이면 1로 변경
            if A[xx][yy] == 0:
                A[xx][yy] = 1
            else:
                A[xx][yy] = 0
    return True

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = [list(map(int, input().rstrip())) for _ in range(N)]
B = [list(map(int, input().rstrip())) for _ in range(N)]

answer = 0
for x in range(N):
    for y in range(M):
        # 다른 숫자인 곳이 있으면
        if not is_same(x, y):
            # 해당 위치부터 3x3 만큼 연산
            if change(x, y):
                answer += 1

# A와 B가 같으면 answer 출력
if A==B:
    print(answer)
# 같지 않으면 -1 출력
else:
    print(-1)

메모리: 30840 KB
시간: 76 ms