[Algorithm] C++/Python 백준 14939번 : 불 끄기

도입글이다. 백준 14939번 “불 끄기” 문제는 10×10 전구 배열을 모두 끄기 위해 최소한의 스위치 누름 횟수를 구하는 퍼즐 문제이다. 간단해 보이지만, 전구를 끄는 과정에서 주변 전구들도 함께 토글(toggle)되는 조건이 추가되어 있어 생각보다 복잡한 탐색 과정을 요한다. 전형적인 BruteForce와 Greedy 기법을 조합해 풀 수 있고, 비트마스킹(bitmask)을 통해 처음 줄의 스위치 누름 상태를 전부 시도하는 방식으로 구현할 수 있다.

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

문제 설명

백준 14939번 “불 끄기” 문제는 다음과 같은 상황을 다루는 전형적인 퍼즐이다. 10행 10열, 즉 총 100개의 전구가 10×10 격자로 늘어서 있고, 각 전구의 상태는 켜짐(‘O’) 또는 꺼짐(’#’) 상태 중 하나이다. 전구를 제어하기 위해서는 전구에 달린 스위치를 누를 수 있는데, 한 전구의 스위치를 누르면 그 전구뿐만 아니라 해당 전구의 상하좌우 전구들도 함께 토글된다. 예를 들어, (r, c) 위치의 전구 스위치를 누른다면, (r, c) 전구는 켜져 있으면 꺼지고 꺼져 있으면 켜지며, 동시에 (r-1, c), (r+1, c), (r, c-1), (r, c+1) 위치의 전구들도 동일하게 상태가 반전된다.

문제의 목표는 모든 전구를 꺼진 상태(’#’)로 만드는 것이다. 하지만 전구를 끄는 것과 동시에 주변 전구가 함께 켜지거나 꺼질 수 있기 때문에, 무작정 “켜져 있는 전구를 보면 바로 스위치를 누른다” 식으로 접근하면 전체를 깔끔하게 끌 수 없는 경우가 생긴다. 특히 이 문제에서는 위에서 아래로 순차적으로 전구를 끄는 그리디(greedy)한 접근이 자주 사용된다. 즉, “어느 줄에서 전구를 어떻게 누르느냐"에 따라 아래 줄부터의 상태가 연쇄적으로 결정된다는 점을 활용하여, 한 줄씩 내려가면서 전구를 꺼나가는 전략을 쓴다.

이때 핵심은 “첫 번째 줄에서 어떤 스위치들을 누를지"를 결정해야 하는데, 첫 번째 줄에서의 선택이 나머지 줄의 행동 패턴을 전부 결정한다. 왜냐하면 ‘위 줄 전구가 켜져 있으면 그 아래 줄 스위치를 눌러서 끈다’는 전략을 사용할 때, 이미 지나간 윗줄은 다시 수정할 수 없기 때문이다. 따라서 첫 번째 줄에 대한 2^10(=1024)가지 경우를 전부 시도하면서, 그 뒤 아래로 이동해가며 필요한 스위치만 누르는 방식을 취한다. 만약 모든 전구를 끄는 데 성공하면 그때 누른 스위치 수가 정답이 된다.
한편, 모든 경우를 시도했음에도 전부 끄지 못할 경우에는 -1을 출력한다.
이 문제는 전구가 단 100개이지만, 첫 줄에 대해 2^10만큼의 경우를 시도하고 각 경우마다 최대 10×10 그리디 탐색을 실행하기 때문에, 시간 복잡도는 대략 2^10 × 100 정도로 충분히 계산 가능하며 1초 안에 빠르게 동작한다. 따라서 BruteForce + Greedy 전략이 매우 효율적이고 간단한 풀이로 이어진다.

접근 방식

초기 상태 입력: 10×10 전구 상태를 입력받는다. 켜진 전구는 ‘O’로, 꺼진 전구는 ‘#‘로 표기된다.
첫 번째 줄 비트마스킹: 첫 번째 줄은 10개의 전구가 있으므로, 각 전구를 누르는지 안 누르는지에 따라 2^10(=1024)가지의 패턴이 생긴다. 이 모든 패턴을 시도해본다.
아래 줄 이동(그리디 적용): 첫 번째 줄의 스위치 누름 패턴을 정한 뒤에는, 두 번째 줄부터 시작하여 바로 위 줄에 켜진 전구가 있으면 그 아래 줄에서 해당 전구의 스위치를 눌러 끈다. 이를 10행까지 반복한다.
최종 상태 확인: 10번째 줄까지 진행했을 때, 마지막 줄이 전부 꺼져 있다면 모든 전구가 꺼졌음을 의미한다. 이때 스위치를 누른 횟수를 기록해두고, 최소값을 갱신한다.
정답 출력: 모든 경우의 수를 탐색했음에도 성공하지 못하면 -1, 성공한 경우가 있다면 그 중 최소 스위치 누름 횟수를 출력한다.

이 접근법은 “한 줄씩 처리를 마치고 나면, 그 윗줄 상태는 더 이상 바꿀 수 없다"는 점을 이용한 전형적인 그리디 형태의 BruteForce 방법이다. 첫 번째 줄에서 나올 수 있는 모든 조합을 전부 시도하므로, 놓치는 경우 없이 해를 찾을 수 있다.

C++ 코드와 설명

아래는 C++ 코드의 예시이다. 첫 번째 줄 스위치 조합에 대해 모두 시도하고, 나머지 줄을 그리디하게 처리한 뒤에 마지막 줄 상태를 확인하는 방식을 구현하였다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

static const int N = 10;
char board[N][N], tempBoard[N][N];

// (r, c) 전구 스위치를 누르면 그 전구와 상하좌우 전구를 토글하는 함수이다.
void toggle(int r, int c) {
    // 상, 하, 좌, 우, 자기 자신을 토글하기 위한 상대 좌표 목록이다.
    int dr[5] = {0, 0, 1, -1, 0};
    int dc[5] = {1, -1, 0, 0, 0};
    
    for(int i = 0; i < 5; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        // 범위를 벗어나지 않는다면 토글한다.
        if(nr >= 0 && nr < N && nc >= 0 && nc < N) {
            // '#'은 꺼짐, 'O'는 켜짐 상태이므로, 서로를 반전시킨다.
            tempBoard[nr][nc] = (tempBoard[nr][nc] == '#') ? 'O' : '#';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 10×10 전구 상태를 입력받는다.
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> board[i][j];
        }
    }

    int answer = INT_MAX;
    // 첫 번째 줄 스위치 패턴을 0부터 2^10 - 1까지 모두 시도한다.
    for(int bit = 0; bit < (1 << N); bit++){
        // 매 시도마다 tempBoard를 원본 board로 복사하여 상태를 초기화한다.
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                tempBoard[i][j] = board[i][j];
            }
        }

        // 현재 스위치 누름 횟수를 저장할 변수이다.
        int pressCount = 0;

        // 첫 번째 줄에 대해 bit를 확인하여, 누를 전구의 위치를 결정한다.
        for(int c = 0; c < N; c++){
            // bit의 c번째 비트가 1이라면 스위치를 누른다.
            if(bit & (1 << c)){
                toggle(0, c);
                pressCount++;
            }
        }

        // 두 번째 줄부터 10번째 줄까지 내려가며, 바로 위 전구가 켜져 있다면 해당 위치 스위치를 눌러 끈다.
        for(int r = 1; r < N; r++){
            for(int c = 0; c < N; c++){
                if(tempBoard[r - 1][c] == 'O'){
                    toggle(r, c);
                    pressCount++;
                }
            }
        }

        // 마지막 줄 상태가 모두 꺼져('#') 있는지 확인한다.
        bool allOff = true;
        for(int c = 0; c < N; c++){
            if(tempBoard[N - 1][c] == 'O'){
                allOff = false;
                break;
            }
        }

        // 전부 꺼졌다면, 최소 스위치 누름 횟수를 갱신한다.
        if(allOff){
            answer = min(answer, pressCount);
        }
    }

    // 모든 전구를 끄는 경우를 하나도 찾지 못했다면 -1을 출력한다.
    if(answer == INT_MAX) cout << -1 << "\n";
    else cout << answer << "\n";

    return 0;
}

코드 동작 단계별 설명

전역 변수 및 보드 배열: board[N][N]에 원본 전구 상태를 저장하고, tempBoard[N][N]에 복사본을 사용하여 시뮬레이션을 수행한다.
toggle 함수: (r, c)를 누르면 자기 자신과 상하좌우의 전구 상태를 모두 반전시킨다.
첫 줄 비트마스크 순회: for(int bit = 0; bit < (1 << N); bit++) 구문을 통해 첫 번째 줄에서 누를 전구들을 결정한다.
아래 줄 그리디 처리: for(int r = 1; r < N; r++)를 돌면서, 바로 윗줄이 켜져 있으면 현재 줄에서 해당 열 스위치를 눌러 끈다.
결과 확인: 마지막 줄 상태를 확인해서 모두 꺼져 있으면 성공으로 간주하고 최소 누름 횟수를 갱신한다.
정답 출력: 모든 패턴을 검사한 후, 만약 성공한 적이 없으면 -1, 그렇지 않으면 최소 스위치 누름 횟수를 출력한다.

Python 코드와 설명

아래는 동일한 로직을 Python으로 작성한 예시 코드이다. Python에서는 bit 연산을 통해 첫 줄 스위치 선택을 시도하고, tempBoard를 리스트로 복사하여 진행한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import sys

input = sys.stdin.readline

N = 10
board = [list(input().strip()) for _ in range(N)]

def toggle(r, c, grid):
    # 상, 하, 좌, 우, 자기 자신을 토글하기 위한 상대 좌표 목록이다.
    dr = [0, 0, 1, -1, 0]
    dc = [1, -1, 0, 0, 0]
    for i in range(5):
        nr = r + dr[i]
        nc = c + dc[i]
        # 범위 안이면 해당 전구 상태를 반전시킨다.
        if 0 <= nr < N and 0 <= nc < N:
            if grid[nr][nc] == '#':
                grid[nr][nc] = 'O'
            else:
                grid[nr][nc] = '#'

def solve():
    answer = float('inf')
    
    # 2^10 가지 첫 줄 스위치 패턴을 전부 시도한다.
    for bit in range(1 << N):
        # 매 시도마다 tempBoard를 board로 복사한다.
        tempBoard = [row[:] for row in board]
        pressCount = 0
        
        # 첫 줄에서 누를 전구 비트 확인
        for c in range(N):
            if bit & (1 << c):
                toggle(0, c, tempBoard)
                pressCount += 1
        
        # 2번째 줄부터 10번째 줄까지 내려가며, 윗줄 전구 상태가 'O'면 스위치 누른다.
        for r in range(1, N):
            for c in range(N):
                if tempBoard[r - 1][c] == 'O':
                    toggle(r, c, tempBoard)
                    pressCount += 1
        
        # 마지막 줄 전부가 '#'인지 확인
        if all(tempBoard[N - 1][c] == '#' for c in range(N)):
            answer = min(answer, pressCount)
    
    # 결과 출력
    return -1 if answer == float('inf') else answer

def main():
    print(solve())

if __name__ == "__main__":
    main()

코드 동작 단계별 설명

입력: board 리스트에 10줄의 전구 상태를 저장한다.
toggle 함수: (r, c) 전구 스위치를 눌렀을 때 (r, c)와 그 상하좌우를 토글한다.
solve 함수:
- bit를 0부터 (1 « 10) - 1까지 순회하여, 첫 줄에서 누를 전구 패턴을 결정한다.
- 이후 2번째 줄부터 내려가면서, 바로 윗줄이 ‘O’라면 현재 줄 전구 스위치를 눌러 끈다.
- 마지막 줄이 모두 꺼져 있다면 누른 횟수를 최소값과 비교하여 갱신한다.
- 최종적으로 최소값을 반환하되, 만약 성공하지 못했다면 -1을 반환한다.
main 함수: solve()의 결과값을 출력한다.

결론

“불 끄기” 문제는 전구 상태를 토글하는 규칙 때문에 자칫 복잡해 보이지만, 첫 번째 줄 스위치를 어떻게 누르느냐가 전체 게임의 흐름을 결정한다는 점에 착안하여 간단히 해결할 수 있는 퍼즐이다. 10×10 격자라는 크기 덕분에 2^10가지 패턴 모두를 시도해도 충분한 시간 내에 해결 가능하다. 만약 문제 규모가 더 커졌다면, 다른 최적화 기법이나 추가적인 pruning 기법이 필요했을 것이다. 하지만 이 문제는 적절한 BruteForce + Greedy 접근만으로도 효율적인 풀이가 가능하다는 점에서, 퍼즐 형태 문제 해결 방법을 잘 보여주는 예시이다. 모두 전구가 꺼지는 과정을 순차적으로 그리디하게 진행하는 아이디어가 매우 직관적이면서도 효과적이라는 점이 특징이다.
앞으로 유사한 전구 토글 문제나 다른 퍼즐 유형에 직면했을 때도, “한 줄씩 처리하여 이미 지나간 줄의 상태를 되돌릴 수 없으므로 첫 번째 줄 패턴을 전수조사한다"는 방법을 다시 적용해볼 수 있을 것이다.