[백준] 동전 뒤집기 1285 - JAVA

문제

https://www.acmicpc.net/problem/1285

생각

각각의 행과 열을 어떨때 뒤집어야 최솟값이 나올지부터 생각해 보았다.
일단 먼저 생각난 것은 i,j번째 동전의 행을 검사해 뒤집힌 동전 갯수보다 뒤집히지 않은 동전 갯수보다 적다면 해당 행을 뒤집어주고 열도 똑같이 검사후 뒤집어 주는 것이다. 역시나 구현후 틀렸고 그 이유는 각각의 뒤집기가 독립적이어야 하는데 한 행을 뒤집고 다른 i,j의 동전에서 이미 뒤집은 동전을 다시 뒤집을 수 있기 때문이다. 즉 처음에 뒤집는 행동이 최선의 행동이란 것을 보장 못한다.

그러면 뒤집는 행동이 최선의 선택이 될려면 어떻게 해야할까??

잘 생각해보면 각각의 행과 열은 뒤집거나 뒤집지 않거나 즉 2가지 상태를 가진다. 즉 N개의 행과열에서는 각각2^N가지의 경우의수가 나오게 된다.
행과 열에 대해서 2가지의 상태를 다 따져본다면 최대 2^40으로 시간초과가 나오게 된다. 그렇다면?? 행과 열중 하나만 모든 경우의수를 구하고 나머지 하나는 해당 경우의수에서의 뒤집힌 동전의 수를 보고 뒤집을지 말지 결정해주면 해결된다.

말이 어려운데 이를 예시로 설명하면 다음과 같다.
1. N이 3일때 행을 뒤집을 수 있는 경우의 수는

• 모든 행을 뒤집지 않거나
• 하나의 행만 뒤집어 주거나 (총 3가지)
• 3개의 행중에 2개의 행을 선택하거나 ($3C2$ = 3)
• 모든 행을 뒤집거나

이런 경우의 수를 가진다.
2. 각각의 경우의 수마다 뒤집힌 동전의 갯수를 구해준다.
3. 열을 뒤집었을때의 뒤집힌 동전의 갯수는 2에서 N - 구한 동전의 갯수와 같다.
4. 2,3번에서 구한 값들 중 최솟값을 구한 후 각각의 경우의 수 중에서 최솟값을 구해준다.

행을 뒤집을 수 있는 경우의 수 구하기

각각의 행마다 2가지의 상태(뒤집거나, 뒤집지 않거나)가 존재하므로 비트마스크를 이용해 구해준다. 즉 비트마스크를 이용해 부분집합을 구해주면 된다.

먼저 나올 수 있는 부분집합의 갯수는 2^N개 이므로 다음과 같이 해준다.

// bit: 0 ~ 2^N - 1
for(int bit=0; bit < (1<<N); bit++) {
	...
}

N이 3일때 bit는 0 ~ 7이 되고 이를 이진수로 나타내면
000 001 010 011 100 101 110 111 이 된다. 이를 활용해 부분집합을 어떻게 구할까??

1을 k만큼 왼쪽 쉬프트한 결과와 bit를 and해주고 결과가 0이 아니라면 k를 부분집합으로 가지고 있다는 뜻이다.

예를들어 bit가 현재 3 즉 011이고 k가 1일때 1<<k의 값은 010이 되고 011(bit)와 010(i)을 and 연산해주면 1이 나오게 된다. 이말의 뜻은 1을 부분집합의 원소로 가지고 있다는 뜻이다. 이를 코드로 나타내면 다음과 같다.

for(int bit=0; bit < (1<<N); bit++) {
	for(int k=0; k<N; k++) {
    	if((bit & (1<<k)) != 0) {
        	// k를 부분집합의 원소로 가지고 있다는 뜻
        }
    }
}

1 ~ N까지 반복문을 돌려준 이유는 bit가 011일때 010도 부분집합의 원소로 가지고 있지만 001도 원소로 가지고 있기 때문에 모든 원소를 구해주기 위함이다.

또한 우리는 선택한 행에 있는 값들을 모두 뒤집어 주어야 하니 다음과 같이 해준다.

for(int bit=0; bit < (1<<N); bit++) {
	for(int col=0; col<N; col++) {
    	for(int k=0; k<N; k++) {
	    	if((bit & (1<<k)) != 0) {
        		// k를 부분집합의 원소로 가지고 있다는 뜻
        	}
    	}
    }
}

이제 각 부분집합에 대한 원소를 모두 구할 수 있으니 구한 원소값에 해당하는 k,col의 동전을 뒤집어주면 된다.

int answer = Integer.MAX_VALUE;
for(int bit=0; bit < (1<<N); bit++) {
	int sum = 0;
	for(int col=0; col<N; col++) {
    	// 뒤집힌 동전 갯수
    	int back = 0;
    	for(int k=0; k<N; k++) {
        	char curr = map[k][col];
	    	if((bit & (1<<k)) != 0) {
				curr = reverse(curr);
        	}
            // 현재 동전이 뒤집혔다면 back + 1
            if(curr == 'T') {
            	back++;
            }
    	}
        // 열을 뒤집었을때랑 뒤집지 않았을때 뒤집힌 동전 갯수중 더 작은 것을 선택
        sum += Math.min(back, N-back);
    }
    // 해당 부분집합에서의 뒤집힌 갯수와 다른 부분집합에서의 뒤집힌 갯수의 최솟값 저장
    answer = Math.min(answer,sum);
}

최종코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  static int N;
  static char[][] map;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    map = new char[N][N];
    for(int i=0; i<N; i++) {
      String s = br.readLine();
      for(int j=0; j<N; j++) {
        map[i][j] = s.charAt(j);
      }
    }
    int answer = Integer.MAX_VALUE;
    for(int bit=1; bit < (1 << N); bit++) {
      int sum = 0;
      for(int j=0; j<N; j++) {
        int back = 0;
        for(int i=0; i<N; i++) {
          char curr = map[i][j];
          if((bit & (1<<i)) != 0) {
            curr = reverse(curr);
          }
          if(curr == 'T')
            back++;
        }
        sum += Math.min(back, N-back);
      }
      answer = Math.min(answer, sum);
    }
    System.out.println(answer);
  }
  public static char reverse(char curr) {
    if(curr == 'T')
      return 'H';
    else 
      return 'T';
  }
}

결론

그리디 문제라고 처음에 그리디쪽으로만 생각을하니 문제가 안풀렸다.. 역시 모든 알고리즘을 생각해 놓고 있어야 겠다.
부분집합을 구할때 백트래킹을 사용할 수 있지만 비트마스킹을 사용하는게 더 효과적인듯 싶다.