[백준 14939] 불 끄기 [C]

백준 - 14939

---

풀이

주어진 예제는 직관적으로 풀이가 가능하지만 주어질 Test Case들을 고려하면 순차적으로 탐색하면서 풀이해야 한다.

우선 첫 번째 행에서 시도해볼 수 있는 모든 경우의 수를 시도한다면, 2~N번째 행에서는 이전 행의 불을 끄면 된다.

 

N번째 행을 검사해서 불이 전부 다 꺼졌다면 입력된 예제가 모두 불이 꺼진 경우이므로 그때 누른 스위치의 개수들의 최솟값을 저장해 출력해주면 된다.

---

소스코드

#include <stdio.h>
#include <string.h>
#include <memory.h>
#define min(a, b) a < b ? a : b
char bulb[10][10], temp[10][10];
const char* lRow = "##########";
int dx[5] = {0, -1, 1}, dy[5] = {0, 0, 0, -1, 1};

void press(int x, int y){
    for (int i = 0; i < 5; i++){
        int nx = x + dx[i], ny = y + dy[i];
		
        if (nx >= 0 && ny >= 0 && nx < 10 && ny < 10)
            temp[nx][ny] = (temp[nx][ny] == '#' ? 'O' : '#');
    }
}
int main(){
    for (int i = 0; i < 100; i++)
        scanf(" %c", &bulb[i/10][i%10]);
	
    int cnt = 101;
    for (int fRow = (1 << 10)-1; fRow >= 0; fRow--){
        int temp_cnt = 0;
        memcpy(temp, bulb, sizeof(bulb));

        for (int fCol = 0; fCol < 10; fCol++)
            if (fRow & (1 << fCol)){
                press(0, fCol);
                temp_cnt++;
            }
		
        for (int nRow = 1; nRow < 10; nRow++)
            for (int nCol = 0; nCol < 10; nCol++)
                if (temp[nRow-1][nCol] == 'O'){
                    press(nRow, nCol);
                    temp_cnt++;
                }
        
        if (!strcmp(temp[9], lRow))
            cnt = min(cnt, temp_cnt);
    }
    printf("%d\n", cnt == 101 ? -1 : cnt);
}

---

출처

14939번: 불 끄기