[백준] 14949번 불 끄기(java)

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

14939번: 불 끄기

브루트포스로 풀 수 있는 문제이다.

플레 난이도답게 아이디어를 생각하기 어려운 문제였다.

 

핵심

스위치를 할 때마다 주변과 현재 위치의 상태가 변하게 된다. 즉 컨트롤하기 어렵다는 문제가 있다.

이를 생각해 보면 위쪽의 경우 아래에서 스위치를 하면 컨트롤할 수 있게 된다 -> 맨 아래는 컨트롤불가

따라서 맨 첫 줄의 모든 경우의 수를 생각하고, 마지막 줄 이전까지의 행을 원하는 대로 바꾼 뒤 맨 마지막줄도 모두 꺼져있다면 성공이다.

 

설계 단계에서 작성한 주석이다.

//우선 1열을 2^10으로 모든 경우의 수를 만든다.
// 이후 2~9까지 위의 방향으로 on -> off  시킨다.
// 마지막 10열에 불이 한 개라도 연켜져야 성공

 

 

정답 코드

import java.util.Scanner;

public class Main {
    static final int SIZE = 10;
    static int[][] move = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static int result = 101;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        boolean[][] map = new boolean[SIZE][SIZE];
        boolean[][] cloneMap = new boolean[SIZE][SIZE];

        for (int i = 0; i < SIZE; i++) {
            String[] line = sc.next().split("");
            for (int j = 0; j < SIZE; j++) {
                if (line[j].equals("O")) {
                    map[i][j] = true;
                }
            }
        }

        for (int c = 0; c < (1 << 10); c++) {
            cloneMap(map, cloneMap);

            int count = 0;
            count = simulation(cloneMap, c, count);

            if (isAllOff(cloneMap)) {
                result = Math.min(result, count);
            }
        }

        System.out.println(result == 101 ? -1 : result);
    }

    private static int simulation(boolean[][] cloneMap, int choose, int count) {
        for (int x = 0; x < SIZE; x++) {
            if ((choose & (1 << x)) != 0) {
                change(cloneMap, 0, x);
                count++;
            }
        }

        for (int y = 1; y < SIZE; y++) {
            for (int x = 0; x < SIZE; x++) {
                if (cloneMap[y - 1][x]) {
                    change(cloneMap, y, x);
                    count++;
                }
            }
        }
        return count;
    }

    private static void change(boolean[][] cloneMap, int y, int x) {
        cloneMap[y][x] = turnOff(cloneMap[y][x]);
        for (int dir = 0; dir < 4; dir++) {
            int moveY = y + move[dir][0];
            int moveX = x + move[dir][1];

            if (isCorrectDirection(moveY, moveX)) {
                cloneMap[moveY][moveX] = turnOff(cloneMap[moveY][moveX]);
            }
        }
    }

    private static boolean isAllOff(boolean[][] cloneMap) {
        for (int x = 0; x < SIZE; x++) {
            if (cloneMap[9][x]) {
                return false;
            }
        }
        return true;
    }

    private static boolean isCorrectDirection(int y, int x) {
        return (0 <= y && y < SIZE && 0 <= x && x < SIZE);
    }

    private static boolean turnOff(boolean status) {
        return !status;
    }

    private static void cloneMap(boolean[][] map, boolean[][] cloneMap) {
        for (int i = 0; i < SIZE; i++) {
            cloneMap[i] = map[i].clone();
        }
    }
}

해설

완전탐색이라 코드자체는 이해하기 쉬운 느낌이다.

우선 처음 입력받은 map을 기준으로 cloneMap을 사용하게 된다.

O -> true , #->false로 초기화

cloneMap을 사용하는 이유는 당연하게도 계속해서 map의 값을 바꿔야 하기 때문이다.

 

첫 줄을 전부 정말탐색하기 위해 2^10의 경우의 수를 모두 수행한다.

ex) 0000000001 -> 맨 마지막 불만 스위치함

이후 2~10번째 줄까지 위의 불이 켜져 있다면 스위치를 하여 불을 꺼준다.

이 과정을 수행하면 당연하게도 1~9번째 줄은 모두 꺼져있게 된다.

이제 마지막줄도 꺼져있다면 전부 끌 수 있는 상태이기에 그때의 카운트와 이전 카운트 중 작은 값을 저장시킨다.

 

 

배운 점

아이디어 자체만 생각한다면 비교적 쉽게 풀 수 있는 문제라고 생각한다.

다만 아이디어를 생각하기가 매우 어렵기에 난도가 있는 문제이다.

개인적으로 매우 좋은 문제라고 생각한다.

이러한 문제를 많이 풀수록 재미있고 논리적 사고력도 늘고 있다는 느낌을 받는다.

또한 요즘 비트연산자를 많이 사용하게 되는데, 이를 잘 활용하면 문제를 쉽게 풀 수 있는 능력이 생기는 것 같다.

프로그래머스를 위주로 풀려고 했으나 백준티어를 플레까지는 찍고 싶다는 느낌을 받았었다.

오늘부로 플레를 찍었기 때문에 다시 프로그래머스 위주로 풀 생각이다.