[자바] 백준 14927 - 전구 끄기 (java)

 문제 : boj14927

---

 

필요 알고리즘 개념

• 브루트 포스, 그리디
  
  • 약간의 브루트 포스 + 그리디가 필요하다. 둘 다 알고리즘이라기보다는 개념적인 부분이라, 구현이 크게 어렵지 않은데 아이디어가 필요한 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  보통 2차원 문제는 1차원으로 먼저 생각하면 더 쉽게 아이디어를 떠올릴 수 있다.

문제를 간단히 하기 위해 1차원에서만 우선 생각해보자.

 

 

A. 1차원에서 생각해보자.

  선택한 위치와 그 좌우까지 연속된 3칸을 골라 해당 3칸에서 1은 0으로, 0은 1로 바꿀 수 있다고 해보자. 이 문제에서 2차원으로 넘어가는 상,하 부분만 없앤 조건이다.

 

  다만, 이번엔 범위를 넘어간 부분은 못 고른다. 즉, 가장 왼쪽의 3개를 고를 때 아래와 같이 온전히 3개가 모두 범위 내에 들어와야 고를 수 있다.

 

  이 경우 어떻게 해결할 수 있을까? 3개의 칸을 좌측부터 우측으로 이동시키면서 (슬라이드 윈도우 알고리즘 처럼) 가장 좌측 값이 1일 경우 무지성으로 변경해버리면 된다.

 

  왜냐하면 어차피 선택의 순서는 관계가 없기 때문에 방향을 고정해도 되기 때문이다. 무슨말이냐면 매번 1->0, 0->1로 변경된다고 생각하지 말고 선택한 3개의 칸을 +1씩 해줬다고 생각해보자. 해당 칸의 최종 상태는 해당 칸을 2로 나눈 나머지가 된다. 즉, 순서를 바꿔서 계산해도 당연히 최종적으로 2로 나눈 나머지가 바뀌진 않는다. 그렇다면 방향을 한쪽으로 고정시키더라도 문제가 없음을 알 수 있다. 그리고 좌측에서 우측으로만 고정시킬 경우, 3칸 중 가장 좌측 칸에 '1'이 있을 때 바꾸지 않는다면 이후 안바꾸고 넘어온 '1'을 바꿀 기회 자체가 없어지므로 무조건 바꾸는 수밖에 없다.

 

  즉, 아래와 같은 순서로 진행하면 되며, 이보다 빠르게 모두 끌 수 있는 방법은 없다. 또한 이하 이미지의 순서를 섞어서 선택하더라도 결과는 동일하다.

 

B. 이번엔 'A'에서 범위가 넘어간 구간도 고를 수 있다.

  이번엔 'A'와 마찬가지로 1차원이지만, 'A'와 다르게 범위를 넘어간 구간도 고를 수 있다. 물론 선택된 위치의 좌우를 함께 변경하는 것이므로 이하 이미지보다 더 좌측으로는 못넘어간다. (즉, 가장 좌측 칸 1개만 바꿀 순 없다. 최소 2칸이 함께 바뀐다.)

 

  이번엔 아래와 같은 배열이 주어졌다.

  이 경우에도 'A'와 동일한 전략을 취하면 될까? 잘 된다. 4번만에 가능했다!

 

  근데, 'A'와 다르게 이번엔 첫번째 칸에 영향을 끼치는게 하나 더 있다. 아래처럼 선택하게 되면 2번만에 가능하다!

 

  즉, 2번째 칸부터는 정해둔 규칙(방향을 고정시켜서 해당 지점을 지나면 더이상 이전값을 바꿀 기회가 없도록 규칙을 정한 방식)을 적용시킬 수 있지만, 첫번째 칸에 대해서는 해당 칸에 영향을 끼칠 수 있는 경우를 모두 봐야 함을 알 수 있다.

 

 

C. 'A'를 2차원으로 확장해보자.

  자 그럼 2차원으로 확장된 이문제에 대해서도 규칙을 정해보자. 우선 2차원에 대해 'A'처럼 규칙을 정해보자. 즉, 범위를 넘어가는 부분은 선택 못하는 것이다. 그리고 방향은 위에서 아래로, 좌측에서 우측으로 고정시키자.

 

  그럼 아래와 같이 맨 위칸(★)을 기준으로 선택하면 된다. 혹은 가장 좌측을 기준으로 해도 된다. 이건 선택하기 나름인데, 각 행에 대해 각 열을 보고 있다면 맨 위칸을 선택해야 한다.

 

 

D. 이번엔 'B' 처럼 범위를 넘어가는 부분도 선택할 수 있다.

  'A' -> 'B'로 넘어갔던 것과 마찬가지다. 'C' -> 'D'로의 확장은 결국 첫번째 줄에 대해서는 적용 가능한 모든 경우를 보고, 그 뒤로는 'C'에서 정한 동일한 규칙을 적용하면 된다. 다만 이번엔 예를들어 첫번째 행의 2번째 열이 1일 경우 적용 가능한 경우가 많다.

 

그렇다면 귀찮으니 그냥 1번째 행에 대해서는 모든 경우를 보기로 하자. 즉, 첫번째 행의 각 열을 중심으로 변경을 할 것인지 말 것인지 선택하면 된다. 그래봐야 2^18 = 262,144 가지 경우만 보면 된다! 그리고 해당 262,144가지경우에 대해 'C'와 동일한 규칙을 적용하면 된다. 그 중 가장 횟수 적게 완성된 경우를 출력해주면 된다. 최종적으로 O(2^N * N^2) 으로 풀 수 있다.

 

 

---

 

예를들어 예제 1은 다음의 과정으로 풀 수 있다.

 

 

코드를 간략히 해설하면 다음과 같다.

private void dfs(boolean[] swt, int idx) {	// 첫번째 행의 각 열을 선택할지 말지가 swt이다.
    if (idx == n) {
        fill(swt);	// 선택이 완료되었으면 규칙대로 진행해보자!
        return;
    }

    dfs(swt, idx+1);	// 현재 idx 선택 안하고 계속 진행
    swt[idx] = true;	// 현재 idx 선택하고 계속 진행
    dfs(swt, idx+1);
    swt[idx] = false;	// 선택한게 끝났으면 다른 경우에 영향을 안끼치게 원래대로 되돌려줘야한다.
}

private void fill(boolean[] swt) {
    int cnt = 0;
    int[][] arr = new int[n][n];
    for (int i = 0; i < n; i++) {	// 입력으로 받은걸 복사한다.
        for (int j = 0; j < n; j++) {
            arr[i][j] = base[i][j];
        }
    }

    for (int j = 0; j < n; j++) {	// 첫번째 행의 모든 경우에 대해 초기 배열을 만든다.
        if (!swt[j]) continue;
        cnt++;
        for (int d = 0; d < 5; d++) {
            int nr = 0+DR[d];
            int nc = j+DC[d];
            if (nr<0||nr>=n||nc<0||nc>=n) continue;
            arr[nr][nc] = arr[nr][nc]^1;    //swap 1, 0
        }
    }

    for (int i = 1; i < n; i++) {	// 규칙에 따라 두번째 행부터 진행하면서
        for (int j = 0; j < n; j++) {
            if (arr[i-1][j] == 0) continue;	// 현재 칸의 위의 칸이 '1'이라면 무조건 변경해준다.
            cnt++;
            for (int d = 0; d < 5; d++) {
                int nr = i+DR[d];
                int nc = j+DC[d];
                if (nr<0||nr>=n||nc<0||nc>=n) continue;
                arr[nr][nc] = arr[nr][nc]^1;
            }
        }
    }

    for (int j = 0; j < n; j++) {	// 현재 이전의 모든 위쪽 행은 0임이 당연히 보장된다. 따라서 맨 마지막줄만 전부 0인지 확인하면 된다.
        if (arr[n-1][j] == 1)
            return;
    }

    answer = Math.min(answer, cnt);	// 모두 끌 수 있었다면 최종 출력할 answer을 최소 카운트 값으로 변경한다.
}

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final StringBuilder output = new StringBuilder();
    private static final int[] DR = {0, 1, -1, 0, 0};
    private static final int[] DC = {0, 0, 0, 1, -1};
    int n;
    int[][] base;
    int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        init();
        boolean[] swt = new boolean[n];
        dfs(swt, 0);
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    private void dfs(boolean[] swt, int idx) {
        if (idx == n) {
            fill(swt);
            return;
        }

        dfs(swt, idx+1);
        swt[idx] = true;
        dfs(swt, idx+1);
        swt[idx] = false;
    }

    private void fill(boolean[] swt) {
        int cnt = 0;
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = base[i][j];
            }
        }

        for (int j = 0; j < n; j++) {
            if (!swt[j]) continue;
            cnt++;
            for (int d = 0; d < 5; d++) {
                int nr = 0+DR[d];
                int nc = j+DC[d];
                if (nr<0||nr>=n||nc<0||nc>=n) continue;
                arr[nr][nc] = arr[nr][nc]^1;    //swap 1, 0
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i-1][j] == 0) continue;
                cnt++;
                for (int d = 0; d < 5; d++) {
                    int nr = i+DR[d];
                    int nc = j+DC[d];
                    if (nr<0||nr>=n||nc<0||nc>=n) continue;
                    arr[nr][nc] = arr[nr][nc]^1;
                }
            }
        }

        for (int j = 0; j < n; j++) {
            if (arr[n-1][j] == 1)
                return;
        }

        answer = Math.min(answer, cnt);
    }

    private void init() throws Exception {
        n = Integer.parseInt(br.readLine());
        base = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                base[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}