알고리즘 풀이 - 백준 1080(행렬, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

0 또는 1로만 이루어진 행렬 A, B가 있을 때, A를 B로 바꾸는 데 필요한 최소 연산의 횟수를 구하는 문제로, 연산은 전체 행렬의 3x3의 부분 행렬을 0이면 1로, 1이면 0으로 모두 바꾸는 것이다.

 

 

2. 풀이

 

각 행 / 열의 모든 위치는 0 또는 1이다. 즉, 기존에 1이었다면 바꾸거나 바꾸지 않거나의 경우로 나뉠 수 있다.

접근 방법은 다음과 같다. 우리는 A → B 행렬로 무조건 변환해야 한다. 따라서 최소의 연산을 통해 변환하려면 서로 다른 부분이 있는 경우에만 연산을 수행하면 된다.

예를 들어 5x5 크기의 A 행렬이 있다고 가정하자. 그러면 각 행/열 위치의 값들이 연산에 의해 변환될 수 있는 최대 횟수는 다음과 같을 것이다.

 

 

즉, 좌측 상단의 (0, 0)은 딱 한 번만 연산으로 변환할 수 있다. 만약 (0, 0)에서 A와 B 행렬이 값이 달라서 연산을 수행했다면 (0, 1)은 이미 (0, 0)에서 1회 연산을 수행했으니, 1번만 추가로 가능하다.

다시 말해, 좌측 상단 부터 A, B 행렬의 일치 여부를 계산하여 연산 수행 여부를 결정하면 모든 위치는 최대 1번만 연산 수행이 가능해진다.

물론 위 그림에선 정가운데 부분 이후 부터는 자기 자신 부터 시작하여 3x3의 부분 행렬을 만들 수 없으니 추가 연산이 필요 없어진다.

 

따라서, (0, 0)부터 시작하여 모든 위치가 일치할 때까지 연산을 수행하는 방식으로 문제를 해결할 수 있다.

 

[문제에 나온 예시의 경우]

① A, B 행렬의 값 확인

 

② (0, 0) 위치 탐색 수행 → 해당 위치의 값이 서로 다르므로 연산 수행하여 3x3 부분 행렬 변환(1회)

 

③ 변환 후 (0, 1)위치 탐색 수행 → 해당 위치의 값이 서로 다르므로 연산 수행하여 3x3 부분 행렬 변환(2회)

 

위와 같이 2회 연산 시, B행렬로 완전히 변환이 가능하다. 이제 코드로 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;
import java.util.*;

public class Main{
    static int n, m;
    static int[][] A;
    static int[][] B;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 주어진 값들 입력
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        A = new int[n][m];
        B = new int[n][m];
        
        // A 행렬 입력
        for(int i=0; i < n; i++){
            String s = br.readLine();
            for(int j=0; j < m; j++){
                A[i][j] = s.charAt(j) - '0';
            }
        }
        
        // B 행렬 입력
        for(int i=0; i < n; i++){
            String s = br.readLine();
            for(int j=0; j < m; j++){
                B[i][j] = s.charAt(j) - '0';
            }
        }
        
        // A -> B로 행렬 전환하기 위해 동작 수행
        int ans = 0;
        for(int i=0; i < n; i++){
            for(int j=0; j < m; j++){
                // 더 이상 부분 행렬 연산이 불가한 위치인데 다르다면, 변환이 불가한 경우!
                if(i >= n-2 || j >= m-2){
                    if(A[i][j] != B[i][j]){
                        System.out.println(-1);
                        return;
                    } else {
                        continue;
                    }
                }
                
                // 값이 다르다면 변경을 수행하고 수행 횟수 +1을 한다.
                if(A[i][j] != B[i][j]){
                    change(i, j);
                    ans++;
                }
            }
        }
        System.out.println(ans);
        br.close();
    }
    
    private static void change(int y, int x){
        // 3x3 행렬 부분을 0이면 1로, 1이면 0으로 변경한다.
        for(int i=y; i <= y+2; i++){
            for(int j=x; j <= x+2; j++){
                A[i][j] = A[i][j] ^ 1;
            }
        }
        
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.