[JAVA] 1285 - 동전뒤집기 💛1 : 어려운 완탐 문제는 시간복잡도를 줄이기 위한 아이디어가 필요. 각각 경우의 수가 2인 요소들로 이루어져 있다면 비트마스킹으로 풀자!

들어가며

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

NxN 개의 동전들이 앞(H) 뒤(T)의 상태를 가진채 입력이 주어진다. 그때 행 또는 열을 뒤집을 수 있는데, 뒤집었을 때 뒷면이 위를 향하는 동전의 최소 개수를 출력하는 문제이다. 딱 읽었을 때 정석적인 완전탐색 문제라고 느꼇다. 하지만 NxN의 동전들을 행과 열별로 재귀적으로 뒤집으면 시간복잡도가 O(2^(N*N))으로 매우 커질 것이다... 그리고 또 동전이 몇개인지 확인하는 로직까지 하면 매우 커진다... 무언가 아이디어가 필요한 문제다.

본문으로

근데.. 도저히 아이디어는 떠올리지 않아. 아래처럼 완탐하는 로직을 작성했다.

public class Main {

    static int N, ret;
    static char[][] coins;

    static void go(int idx) {
        if (idx > N) {
            return;
        }
        int tCnt = findT();
        ret = Math.min(ret, tCnt);

        for (int i = idx; i < N; i++) {
            turnColum(i);
            go(i + 1);
            turnColum(i);
        }

        for (int j = idx; j < N; j++) {
            turnRow(j);
            go(j + 1);
            turnRow(j);
        }
    }

    static void turnColum(int idx) {
        for (int i = 0; i < N; i++) {
            if (coins[i][idx] == 'T') {
                coins[i][idx] = 'H';
            } else {
                coins[i][idx] = 'T';
            }
        }
    }

    static void turnRow(int idx) {
        for (int i = 0; i < N; i++) {
            if (coins[idx][i] == 'T') {
                coins[idx][i] = 'H';
            } else {
                coins[idx][i] = 'T';
            }
        }

    }

    static int findT() {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (coins[i][j] == 'T') {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        coins = new char[N][N];

        for (int i = 0; i < N; i++) {
            String line = bf.readLine();
            for (int j = 0; j < N; j++) {
                coins[i][j] = line.charAt(j);
            }
        }

        ret = Integer.MAX_VALUE;
        go(0);

        System.out.println(ret);

    }
}

당연하게도 결과는 시간초과 ㅋㅋ...

---

어떻게 해야할까? 여기서 시간복잡도를 줄일 수 있는 포인트는 아래와 같았다.

현재 열의 뒤집는가 안뒤집는가 경우는 현재 열의 뒷면의 개수 혹은 N - 뒷면의 개수 아니겠는가!
그렇다면 경우 행만 뒤집으면 열은 min(뒷면의 개수, N - 뒷면의 개수)로 최적해를 구할 수 있다.

시간복잡도도 절반으로 줄어들어서 도전해볼만 하다!

그렇다면 정답 코드는 아래와 같다.

public class Main {

    static int N, ret;
    static int[] coins;

    static void go(int here) {
        if (here > N) {
            int sum = 0;
            for (int i = 1; i <= (1 << N); i *= 2) {
                int cnt = 0;
                for (int j = 0; j < N; j++) {
                    if ((coins[j] & i) != 0) {
                        cnt++;
                    }
                }
                sum += Math.min(cnt, N - cnt);
            }
            ret = Math.min(ret, sum);
            return;
        }

        go(here + 1);
        coins[here] = ~coins[here];
        go(here + 1);
    }


    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        coins = new int[N + 4];

        for (int i = 0; i < N; i++) {
            String line = bf.readLine();
            int value = 1;
            for (int j = 0; j < N; j++) {
                if (line.charAt(j) == 'T') {
                    coins[i] |= value;
                }
                value *= 2;
            }
        }
        ret = Integer.MAX_VALUE;

        go(0);
        System.out.println(ret);
    }
}

---

비트마스킹을 적극적으로 활용했다. 일단 동전을 입력받는 부분인 아래 로직을 보면 행을 탐색하며 T(뒷면)일때만 value를 OR연산자 해주고 있다.

for (int i = 0; i < N; i++) {
            String line = bf.readLine();
            int value = 1;
            for (int j = 0; j < N; j++) {
                if (line.charAt(j) == 'T') {
                    coins[i] |= value;
                }
                value *= 2;
            }
        }

아래 그림을 보면 조금 더 이해가 쉬울 것이다. 즉 T인 곳만 비트를 킨 것처럼 생각해서, HHT -> 0 * 2^0 + 0 * 2^1 + 1 * 2 ^ 2 = 4 식으로, 이차원 배열을 하나의 배열로 저장한다. 그래서 한 행을 하나의 숫자로 저장하기 때문에 coins 배열의 인덱스를 증가시킨다면 열을 탐색한다고 볼 수 있다.

---

아래 코드는 재귀적코드의 흐름이다. here을 + 1 로 증가시키며 재귀적으로 탐색한다. 그리고 뒤집는 거는 비트 반전 연산자(~)를 이용해서 뒤집어 준다. 만약 이렇게 안했으면 if(coins[i] == 'T') coins[i] = 'H' 식의 코드를 작성해야 했을 것이다.

go(here + 1);
        coins[here] = ~coins[here];
        go(here + 1);

사실 ~a = - (a + 1) 이다. 뒤집으면 다른 32bit에 해당하는 비트들도 뒤집어져 버린다.

하지만 재귀함수의 범위를 보면 알 수 있듯이, 우리는 우리가 직접 'T'는 비트를 켰고, 'H'는 비트를 끄며 의도적으로 입력을 받은 부분까지만 탐색을 한다. 그리고 여기서 바로 이 문제의 핵심 아이디어가 나온다. 이 기저조건에 걸렸다는 뜻은, 원하는 행을 뒤집은 경우에서 열에 대한 동전들의 뒷면만 확인하며, Math.min(cnt, N - cnt) 라는 아이디어로 열의 최적해를 바로 구해준다.

if (here > N) {
            int sum = 0;
            for (int i = 1; i < (1 << N); i *= 2) {
                int cnt = 0;
                for (int j = 0; j < N; j++) {
                    if ((coins[j] & i) != 0) {
                        cnt++;
                    }
                }
                sum += Math.min(cnt, N - cnt);
            }
            ret = Math.min(ret, sum);
            return;
        }

---

위의 로직에서 처음에는 for(int i = 1; i <= (1 << N); i*=2) 로 범위를 설정했었는데, 틀렸었다. 비트는 0번부터 시작하니 <=로 N을 포함시키면 범위가 틀려진다. N이 3까지라면 001, 010 식으로 저장되어있을 것이기에 0번째 1번째 2번째 비트까지만 검사해줘야한다. 그러니 <N 까지로 설정해서 범위 신경써주는 거 잊지말자.

마무리하며

골드 1,2 나 플레문제들은 문제를 읽으며 자연스럽게 떠오르는 1차원적인 풀이로는 절대로 풀리지 않는 것 같다. 시간복잡도를 줄이는 이런 아이디어를 코테라는 제한적인 시간에 어떻게 떠올리지...? 시간을 많이 준다면 여유롭게 이것저것 생각해볼텐데... 제한된 시간안에 떠올리는 거는 아직 너무 힘들다. 솔직히 좀 벽을 만난 느낌이다. 비트마스킹도 아직 너무 어색하다🥲

그래도 헤멘 만큼 내 땅이니!! 열심히 헤메보자! 아자자.