[그리디] 코딩테스트 문제 TIL (행렬) - 백준 1080번

말하는 감자·2024년 12월 18일

TIL algorithm baekjoon greedy python 그리디 백준 알고리즘 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

37/67

1. 오늘의 학습 키워드

그리디 알고리즘

2. 문제: 1080. 행렬

단계: 🥈실버 1단계
주제:
- 그리디 알고리즘
출처: https://www.acmicpc.net/problem/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을 출력한다.

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

예제 입력 3 복사

1 1
1
0

예제 출력 3 복사

-1

예제 입력 4 복사

3. 문제 풀이

Step1. 문제 이해하기

0과 1로만 이루어진 행렬 A와 B가 있습니다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 문제입니다.

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

입출력 조건을 살펴보겠습니다.

Input:
- 첫째 줄에 행렬의 크기 N, M이 주어집니다. N과 M은 50이하의 자연수입니다.
- 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬B가 주어집니다.
- 세로, 가로 이중 반복문을 탐색하더라도 시간 복잡도상 충분한 여유가 있는것을 알 수 있습니다.
Output:
- 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 출력합니다. 만약 바꿀 수 없다면 -1을 출력합니다.

Step2. 문제 분석하기

A를 B로 바꾸기 위해 제일 왼쪽 위(0,0)에서부터 탐색을 해야 합니다. 현재 위치에서 A와 B가 다르다면, 그 차이를 줄이기 위해 해당 위치를 포함하는 3x3 부분 행렬을 뒤집어야 합니다.

주어진 문제는 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 문제였습니다. 그런데 연산은 3x3크기의 부분 행렬을 뒤집는 것입니다. 당장 현재 위치에서 다르다면 해당 연산을 바로 수행해야 합니다.

즉, 각 단계(현재 위치)에서 값이 다르다면 바로 연산을 수행하는게 최소 횟수가 될 수 있다는 것입니다.

왜냐하면 현재 위치에서 값을 다르게 만드는 문제를 해결하지 않고 다음으로 넘어가면, 나중에 다시 돌아와야 하거나 더 많은 연산이 필요해지기 때문입니다. 즉, 현재 위치에서 A와 B의 차이를 바로 해결하지 않으면, 이후 다른 위치에서 수정 작업이 중복되거나, 결과적으로 더 많은 연산이 필요하게 됩니다.

따라서, 현재 위치에서 A와 B의 차이를 발견하면 즉시 3×3 부분 행렬을 뒤집는 것이 최소 연산 횟수를 보장하는 그리디 전략이 됩니다. 이 방식은 문제의 조건에서 제시된 "최소 연산 횟수"를 충족시키는 데 적합합니다.

그리디 알고리즘의 특징을 기반으로 정리하자면 다음과 같습니다.

탐욕적 선택 속성:
- 현재 위치에서 A와 B의 값이 다르면, 해당 위치를 포함하는 3x3 부분 행렬을 뒤집는 것이 최선입니다.
최적 부분 구조:
- 각 3x3 부분 행렬을 뒤집는 연산은 나머지 영역에 영향을 미치지 않고, 현재 탐색 영역을 완전히 해결합니다. 즉, 문제를 작은 문제로 나누어 해결합니다.

Step3. 코드 설계

입력 처리:
- N, M: 행렬의 크기를 입력받습니다.
- 행렬 A와 B를 입력받아 각각 2차원 리스트로 저장합니다.
3×3 부분 행렬 변환 함수:
- convert_matrix(i, j, arr)는 행렬 arr의 i,j를 좌상단으로 하는 3×3 부분 행렬을 뒤집습니다.
- 행렬의 각 원소를 1 - arr[x][y]로 반전시킵니다.
그리디 탐색:
- i=0부터 N−3, j=0부터 M−3까지 탐색하며, 행렬 A와 B를 비교합니다.
- $A[i][j] \neq B[i][j]$ 인 경우, 해당 위치에서 3×3 변환 연산을 수행하고, 변환 횟수를 증가시킵니다.
결과 검증:
- 모든 변환 연산이 끝난 후, 행렬 A와 B를 비교하여 일치 여부를 확인합니다.
- 일치하지 않는다면 −1, 일치한다면 변환 횟수 cnt를 출력합니다

Step4. 코드 구현

import sys
N, M = map(int, sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
B = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
cnt = 0
flag = True

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):
        if A[i][j] != B[i][j]:
            convert_matrix(i, j, A)
            cnt += 1
for i in range(N):
    for j in range(M):
        if A[i][j] != B[i][j]:
            flag = False
print(-1 if not flag else cnt)

시간 복잡도: $O(N \times M)$
결과:

4. 마무리

이 문제는 그리디 알고리즘을 활용하여 최소 연산 횟수를 구하는 문제로, 현재 위치에서 값을 다르게 만드는 문제를 즉시 해결하는 것이 최적의 선택입니다. 이를 통해 중복된 작업을 방지하고, 효율적으로 변환 연산을 수행할 수 있습니다. 코드의 시간 복잡도는 $O(N \times M)$ 로 문제의 제약 조건을 만족합니다.