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을 출력한다.
"""
알고리즘
루프를 돌면서 A 인덱스 값과 B 인덱스 값을 비교하고 다르면 (A 인덱스 값이 좌측 최상단인) 3x3 부분 행렬을 뒤집는다
다 돌고나서 값이 같다면 count, 아니라면 -1을 출력한다.
"""
def reverse(x,y):
global A
for i in range(x,x+3):
for j in range(y,y+3):
if A[i][j] == 0:
A[i][j] = 1
else:
A[i][j] = 0
N,M = map(int,input().split())
A = [list(map(int,list(input()))) for _ in range(N)]
B = [list(map(int,list(input()))) for _ in range(N)]
count = 0
# A의 값과 B의 값이 동일한지 루프를 돌면서 확인하고, 다르다면 3x3 행렬을 뒤집는다.
for i in range(N-2):
for j in range(M-2):
if A[i][j] != B[i][j]:
reverse(i,j)
count+=1
# A랑 B가 동일한지 검사
def check():
for i in range(N):
for j in range(M):
#동일하지 않다면 -1을 출력하고 종료
if A[i][j] != B[i][j]:
print(-1)
return
#동일하다면 count 값을 출력
print(count)
check()그리디 알고리즘이란?
그리디는 최적의 답을 내는 사용 조건으로 최적 부분 구조와 탐욕적 선택 속성이 있어야 한다.
최적 부분 구조: 각 부분 문제의 최적해만 있으면, 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 최적 부분 구조 조건을 성립한다고 함
탐욕적 선택 속성: 탐욕적으로만 선택을 해도 최적해를 구할 수 있음. <예를 들어 도착했을 때 최댓값을 구하려고 할 때, 맞닥뜨리는 양갈래길마다 값이 큰 길만 선택> 다른 특징으로는, 한번 선택한 것은 번복하지 않고,항상 최적해를 보장하지 않기 때문에, 정당성 증명 과정을 거쳐야 한다.
풀이
일단 첫번째로 든 의문점은 “뒤집는 순서가 결과값에 영향을 주지 않을까?” 였다.
그리디 알고리즘 통해서 최소값이 얻어진다고 확신을 가질 수 없었기 때문에 섣불리 사용할 수가 없었다.
구글링 해봤을 때 나랑 비슷한 고민을 했거나, 아니면 시원한 답변을 가진 블로그 글을 찾기 어렵던 중 가장 도움이 되었던게 아래 블로그이다.
일단 여기 나온 내용을 정리해보자면, 이 문제의 목적은 ‘뒤집기’이고, 문제의 핵심은 이 뒤집기를 ‘최소화'하는 것이다.
결국 A를 B랑 동일하게 만들어야 하기에, 다른 부분이 나오면 뒤집기는 한다!
하지만 이렇게 확정지은 칸을 다시 뒤집어서 번복하거나, 재차 뒤집는 일은 없어야 한다는 의미이다.
그 이유는 뒤집기의 속성을 인지하면 이해할 수 있다.
2번 뒤집으면 원래대로 돌아오고, 3번 뒤집으면 1번 뒤집는것과 동일하기에, 2번 이상 뒤집는 것은 ‘뒤집기를 최소화'하려는 목적에 어긋나기 때문이다.
그래서 반복문으로 A 행렬을 순서대로 살펴보면서 만약 B 행렬의 칸과 다를 경우에 뒤집는다.
문제의 조건이라서 어쩔 수 없이 3x3만큼 뒤집기는하지만, 확정짓게 되는 것은 “한 칸”이다.
확정을 지은 이 ‘한 칸’이 번복되면 안된다는 의미이다.
만약 3x3 안에 있는 다른 칸들이 어떻게 얻어걸려서 B 행렬의 칸과 같아지더라도, 이는 위의 ‘한 칸'처럼 확정되었다고는 할 수 없다. 얼마든지 다른 칸의 순서에 3x3안에 또 들어가게 되면서 다시 뒤집힐 수도 있다.
대신 루프의 자신 차례에서 확정을 받게 되면, 다시 뒤집힐 일은 없다.
이 루프를 반복하고 나면 A 행렬은 의도했던대로 B 행렬과 똑같아졌던가, 아니면 그럼에도 똑같지 않을 수 있다.
느낀 점:
블로그를 서칭하면서 아이디어를 캐치하고 풀기는 풀었지면 영 찝찝함이 남아있기는 하다.
그리디인것을 알고서도 감이 안잡혔는데, 만약 알고리즘 분류가 그리디인것을 몰랐다면 과연 풀 수 있었을까 싶다. (엄청나게 많은 시행착오를 겪었을 것 같다)
그래도 확실히 이런 문제를 맞닥뜨리면서 그리디 알고리즘의 본질적인 원리를 생각해볼 수 있었다는게 꽤나 큰 순기능이었던 것 같다.
