[JAVA/자바][백준 14939] 불 끄기

문제

---

 

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

14939번: 불 끄기

 

 

접근 방법

---

무작정 구현을 시작했는데 해결하지 못했다. 이후 검색을 해보며 힌트를 얻었다.

비트마스킹을 이용한 풀이방법밖에 찾지 못했다. 나는 비트마스킹을 잘 모르기에 비트마스킹을 사용하지 않고 그냥 빡세게 구현했다.

원리는 이렇다.

• 같은 스위치를 여러 번 누르지 않는다.
  • 같은 행위를 반복하면 최적의 해를 구할 수 없다.
• 완전 탐색으로 100개의 전구를 켜고 끄는 경우를 찾으면 O(2^100)이다.
  • 시간초과가 발생한다.
• 한 가로 줄은 맞닿아 있는 가로 줄에만 직접적으로 영향을 끼친다.
  • 즉, 다음 가로 줄에서 앞선 가로줄의 불을 모두 꺼줄 수 있다.

따라서, 첫 가로 줄의 행동이 정해지면 자동으로 2번째 가로 줄의 행동이 정해지고, 10번째 줄까지 정해지게 된다.

• 이 경우에는 O(2^10) * 나머지 줄 계산(= O(90) * 한 칸 계산)으로, 완전 탐색에 비해 시간을 많이 단축한다.

이전 가로 줄의 전구를 모두 껐기 때문에, 마지막 줄에 대해서만 확인하면 된다.

• 마지막 줄에 불이 켜진 전구가 존재하면 불가능한 경우에 해당한다.
• 모두 불이 꺼져 있으면 성공한 경우에 해당한다.

 

 

풀이

---

1. 첫 번째 줄의 모든 경우의 수를 구해 List에 저장한다.
   • makeFirstLine()
2. 첫 번째 가로 줄의 모든 경우의 수(2^10 = 1024)에 대해 탐색한다.
3. 각 탐색의 경우는 독립적이므로, tmpBoard에 board를 복사한다.
   • copy()
4. 해당하는 경우에 맞게 1번째 가로줄의 스위치를 누른다.
   • cnt++를 통해 스위치 클릭 수 계산
   • pushSwitch()
     • dX, dY 배열을 통해 주변 전구 상태 갱신
5. 2 ~ 10 번째 줄에서 이전 줄에 대한 소등 작업을 진행한다.
6. 마지막 줄을 확인하여 해당 경우를 마무리 한다.
   • cannotMake 확인
7. 3 ~ 6 번 작업을 2번에 해당하는 경우만큼 모두 탐색한다.

 

 

코드

---

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

public class Main {
    private static int[] dX = {0, -1, 0, 1, 0};
    private static int[] dY = {0, 0, -1, 0, 1};
    private static char[][] board;
    private static char[][] tmpBoard;
    private static List<String> firstLine = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        board = new char[10][10];
        for (int i = 0; i < 10; i++) {
            board[i] = br.readLine().toCharArray();
        }
        tmpBoard = new char[10][10];

        int answer = 101;

        makeFirstLine(1, "", 1);
        makeFirstLine(1, "", 2);

        for (String e : firstLine) {
            int cnt = 0;
            copy();

//1번째 줄 선택for (int i = 0; i < 10; i++) {
                if (e.charAt(i) == 'O') {
                    pushSwitch(0, i);
                    cnt++;
                }
            }

//2~9번쨰 줄 선택for (int i = 1; i < 10; i++) {
                for (int j = 0; j < 10; j++) {
                    if (tmpBoard[i - 1][j] == 'O') {
                        pushSwitch(i, j);
                        cnt++;
                    }
                }
            }

//10번째 줄 확인if (!cannotMake()) {
                answer = Math.min(answer, cnt);
            }
        }
        if (answer == 101) {
            System.out.println(-1);
            return;
        }
        System.out.println(answer);
    }

    private static void makeFirstLine(int depth, String output, int mode) {
        if (mode == 1) {
            output += 'O';
        } else {
            output += 'X';
        }
        if (depth == 10) {
            firstLine.add(output);
            return;
        }
        for (int i = 0; i < 2; i++) {
            makeFirstLine(depth + 1, output, i);
        }
    }

    private static void copy() {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                tmpBoard[i][j] = board[i][j];
            }
        }
    }

    private static void pushSwitch(int x, int y) {
        for (int k = 0; k < 5; k++) {
            int nextX = x + dX[k];
            int nextY = y + dY[k];
            if (nextX >= 0 && nextX < 10 && nextY >= 0 && nextY < 10) {
                if (tmpBoard[nextX][nextY] == 'O') {
                    tmpBoard[nextX][nextY] = '#';
                } else {
                    tmpBoard[nextX][nextY] = 'O';
                }
            }
        }
    }

    private static boolean cannotMake() {
        boolean flag = false;
        for (int i = 0; i < 10; i++) {
            if (tmpBoard[9][i] == 'O') {
                flag = true;
                break;
            }
        }
        return flag;
    }
}