[Python] 백준 풀기 1080 - 행렬

파이썬 백준 1080번

실버 1

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

1080번: 행렬

 

 

 

 

 

문제 보기

분류: 그리디 알고리즘

 

 

 

 

 

문제 풀기

처음에 문제를 정확하게 읽지 않아 A 와 B 에서 같지 않은 부분만 3x3 으로 변경이 가능하다고 생각하여 최소 횟수로로 변경 가능한 위치를 찾느라 좀 헤메었다.

제시된 문제의 연산 규칙에 따라 3x3 부분의 1열1행에 위치한 원소가 다르면 무조건 3x3 을 뒤집으면 된다.

다 뒤집어 봤는데도 같지 않으면 -1 이고, 뒤집을 수 없어도 -1 을 출력한다.

 

 

이중 for loop 을 돌리면서 모든 행렬의 A, B 원소를 비교한다.

다른 원소의 위치가 발견되면 3x3 구간의 모든 원소를 뒤집는다.

모든 원소들을 탐색하고 나면 A 와 B 를 비교해보고 같지 않으면 -1 을 출력. 그렇지 않으면 누적된 연산 횟수를 출력한다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnFlip(i, j):           ## 모든 3 x 3 위치 뒤집기.
    for x in range(i, i + 3):
        for y in range(j, j + 3):
            matrix_A[x][y] = 1- matrix_A[x][y]

def fnMinConversion(N, M):
    opertaion_count = 0
    for i in range(N-2):            ## A 와 B 의 같은 위치의 값을 비교하기 위한 이중 for loop.
        for j in range(M-2):
            if matrix_A[i][j] != matrix_B[i][j]:            ## A 와 B 가 다른 값을 갖으며 if 진입.
                fnFlip(i, j)            ## 0 -> 1, 0 -> 1 함수 실행.
                opertaion_count += 1            ## 뒤집기 연산이 실행되었기에 +1.
    
    if matrix_A != matrix_B:            ## 모든 검사 및 연산이 끝났는데 값이 같지 않으면 -1 출력.
        print(-1)
    else:           ## 연산 횟수 출력.
        print(opertaion_count)


if __name__ == "__main__":
    N, M = map(int, inputdata().split())
    matrix_A = [list(map(int, inputdata().strip())) for _ in range(N)]
    matrix_B = [list(map(int, inputdata().strip())) for _ in range(N)]
    
    fnMinConversion(N, M)