• 개인 공부 목적으로 작성한 포스팅입니다.
  • 아래 출처를 참고하여 작성하였습니다. :)

문제: 불 끄기

문제해결 아이디어

  • 첫 줄만 어떤 버튼을 누를 지 결정하면
  • 두 번째 줄부터는 윗 줄의 전구가 켜져있는지 여부에 따라서 현재 전구를 누를지 말지를 그리디하게 정할 수 있습니다.

따라서 탐색 범위는 첫 줄을 클릭하는 모든 경우의 수(2^10)만 구하면 나머지 칸을 눌러야 할 지 말아야 할지는 알아서 결정됩니다.

  • 그렇게 첫 줄의 정보가 완성되면, 두 번째 줄부터 나머지 줄까지 전부 순회를 하면서 윗 칸이 켜져 있으면 자기 자신을 누르면 됩니다.

코드

import java.io.*;


public class Main {

    public static final int[] dy = {-1,1,0,0};
    public static final int[] dx = {0,0,-1,1};
    public static final int OFF = -1;
    public static final int ON = 1;
    public static final int BOARD_SIZE = 10;
    public static int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
    public static int[][] tmpBoard = new int[BOARD_SIZE][BOARD_SIZE];

    public static boolean isSafe(int y, int x) {
        return 0 <= y && y < BOARD_SIZE && 0 <= x && x < BOARD_SIZE;
    }

    public static void toggle(int y, int x) {
        for (int dir = 0; dir < 4; ++dir) {
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if (isSafe(ny, nx)) {
                tmpBoard[ny][nx] = -tmpBoard[ny][nx];
            }
        }

        tmpBoard[y][x] = -tmpBoard[y][x];
    }

    public static void reset() {
        for (int i = 0; i < BOARD_SIZE; ++i) {
            for (int j = 0; j < BOARD_SIZE; ++j) {
                tmpBoard[i][j] = board[i][j];
            }
        }
    }

    public static boolean isAllOff() {
        for (int i = 0; i < BOARD_SIZE; ++i) {
            for (int j = 0; j < BOARD_SIZE; ++j) {
                if (tmpBoard[i][j] == ON) {
                    return false;
                }
            }
        }
        return true;
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < BOARD_SIZE; ++i) {
            String row = br.readLine();

            for (int j = 0; j < BOARD_SIZE; ++j) {
                char c = row.charAt(j);

                if (c == '#') {
                    board[i][j] = OFF;
                } else {
                    board[i][j] = ON;
                }
            }
        }

        int ans = Integer.MAX_VALUE;

        // 첫째줄 상태
        for (int state = 0; state < (1 << BOARD_SIZE); ++state) {

            int cnt = 0;
            reset();

            for (int j = 0; j < BOARD_SIZE; ++j) {
                if ((state & (1 << j)) > 0) {
                    cnt++;
                    toggle(0, j);
                }
            }

            for (int i = 1; i < BOARD_SIZE; ++i) {
                for (int j = 0; j < BOARD_SIZE; ++j) {
                    // 임의로 클릭한 첫 번째 줄부터 꺼야할 전구는 꺼야하므로 i-1
                    if (tmpBoard[i-1][j] == ON) {
                        toggle(i, j);
                        cnt++;
                    }
                }
            }

            if (isAllOff()) {
                ans = Math.min(ans, cnt);
            }
        }

        if (ans == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(ans);
    }
}