[백준 BOJ / Python] 1080번 행렬
문제 0과 1로만 이루어진 행렬 A,B가 있다. 이때 행렬 A를 B로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제이다. 행렬 변환 연산은 3*3 부분 행렬에 있는 모든 원소를 0은 1로 1은 0으로 바꾸는 것이다. 만약 바꿀 수 없다면 -1를 출력한다. 풀이 N*M 행렬을 모두 순회하면서 (i,j)값이 A와 B가 다른 경우, A의 (i,j)부터 3*3 부분행렬을 뒤집어 (i,j)값이 동일하도록 바꾸어 준다. 이때 (i,j)를 시작점으로 3*3 부분행렬을 뒤집어주는 이유는 앞의 이미 B와 동일한 부분은 건들지 않으면서 뒤의 다른 부분은 다시 뒤집을 수 있기 때문이다. 가능한 모든 부분행렬을 한번씩 살펴봄으로써 뒤집어야하는 최소 횟수를 구할 수 있다. 알고리즘 for문을 통해 3*3 영역을 뒤집을 수 있는..
Study/Coding Test
2023. 3. 2.