알고리즘 풀이 - 백준 1285(동전 뒤집기, 그리디(Greedy))

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

NxN 행렬로 동전이 앞 뒤로 놓여 있는 경우 1회 연산에 1행 또는 1열의 N개 동전을 모두 뒤집을 수 있을 때, 뒷면이 위를 향하는 동전의 개수를 최소로 하는 연산의 수를 구하는 문제

 

 

2. 풀이

 

각 동전은 행 또는 열을 바꿀 때, 그 결과가 바뀔 수 있다. 즉, 모든 동전은 2번의 변환이 가능하다.

따라서 접근 방식은 다음과 같다. 3x3 크기의 행렬로 동전이 있다고 가정하자.

그러면, 행을 바꾸는 경우는 아래와 같이 총 7가지가 있다.

① 모든 행을 바꾸지 않는 1가지
② 모든 행을 다 바꾸는 1가지
③ 2개의 행을 골라 바꾸는 3가지
④ 1개의 행을 골라 바꾸는 3가지

 

그러면, 행을 변경했을 때, 열을 기준으로 동전을 바꿀 수 있는 경우만 남게 된다. 그러면, 각 열에 대해서 현재 열을 변환한 경우와 변환하지 않은 경우를 모두 계산이 가능하다.

왜냐하면, 하나의 열의 동전의 총 개수는 N개로 동일하기 때문에 뒤집은 경우와 뒤집지 않은 경우 중 더 적은 경우로 계산을 하면 되기 때문이다.

 

즉, 다시 설명하면 다음과 같다.

① 각 행에 대해 동전의 상태를 변경할 수 있는 모든 경우에 대해 아래의 연산을 수행한다.(비트마스크로 반복문 수행)
② 각 열에 대해 반복문 수행하며 현재 위치의 비트가 1이라면 한 번 뒤집는다.
③ 위에서 행을 기준으로 뒤집는 경우를 완수했으니, 현재 열의 뒤집힌 동전의 개수를 구한다.
④ 현재 열의 동전의 총 개수는 N개 이므로 현재 열의 뒤집힌 동전의 개수가 A개라면 현재 열을 뒤집는 경우는 N-A개, 현재 열을 뒤집지 않는 경우는 A개의 뒤집힌 동전이 있게 된다.
⑤ 전체 열에 대해 최소의 뒤집는 동전의 개수를 구하여 모두 더하면 현재 행을 뒤집는 기준으로 최소의 뒤집힌 동전의 전체 개수를 구할 수 있다.

 

위에서 ①번의 비트값을 기준으로 ② ~ ⑤를 반복하여 전체 뒤집힌 동전의 최소 개수를 구하여 문제를 해결한다.

 

 

3. 코드

 

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

import java.io.*;

public class Main{
    static int n;
    static int[][] map;
    public static void main(String[] args) throws IOException{
        // 주어진 값 저장
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        
        for(int i=0; i < n; i++){
            String s = br.readLine();
            for(int j=0; j < n; j++){
                char c = s.charAt(j);
                if(c == 'T'){
                    map[i][j] = 1;
                }
            }
        }
        
        int ans = 400;
        // 행을 뒤집을 것인가 뒤집지 않을 것인가를 비트마스크로 결정
        // n=3일 때, 예를 들어 001 이라면 3번째 행만 뒤집는다는 의미이다.
        for(int bit=0; bit < (1<<n)-1; bit++){
            int sum = 0;
            
            // 현재 비트값에 대해 모든 열에서 탐색 수행
            for(int x=0; x < n; x++){
                int tail = 0;
                
                // 각 열의 행을 뒤집거나 뒤집지 않거나 수행
                for(int y=0; y < n; y++){
                    int cur = map[y][x];
                    // 뒤집는다.(비트가 1이면)
                    if((bit&(1<<y)) != 0){
                        cur = flip(y, x);
                    }
                    // tail의 수를 찾는다.
                    if(cur == 1) tail++;
                }
                // 열을 뒤집거나 뒤집지 않거나의 경우를 상정하여 더 작은 경우를 더함!
                sum += Math.min(tail, n-tail);
            }
            if(ans > sum) ans = sum;
        }
        System.out.println(ans);
        br.close();
    }
    
    private static int flip(int y, int x){
        return map[y][x] ^ 1;
    }
}

 

 

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