[BEAKJOON] 16918 - 봄버맨

오늘 풀어본 문제는 Beakjoon online judge 사이트에 있는 16918번 문제 봄버맨을 풀어보았다.

 

 

 

일단 손으로 직접 테스트 케이스를 가지고 진행해보았다.

 

주어진 테스트 케이스는 다음과 같다.

6 7 3

 .  .  .  .  .  .  . 

 .  .  . O .  .  .

 .  .  .  . O .  .

 .  .  .  .  .  .  .

O O .  .  .  .  .

O O .  .  .  .  .

앞으로는 ' . ' 을 쓰면 보기 어려워서 'X' 를 쓰도록 하겠다.

 

time(N)	1	2	3	4	5
map[][]	XXXXXXX XXXOXXX XXXXOXX XXXXXXX OOXXXXX OOXXXXX	OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO	OOOXOOO OOXXXOO OOOXXXO XXOOXOO XXXOOOO XXXOOOO	OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO	XXXXXXX XXXOXXX XXXXOXX XXXXXXX OOXXXXX OOXXXXX

이 문제를 처음 읽어봤을 때, 구현문제인가 싶어, 코드를 머리속으로 생각하고 있는데, 뭔가 너무 비효율적인것 같았다.

1초와 5초가 동일하고, 2초와 4초가 동일한것을 확인하였다.

그래서 6초 7초 8초도 직접 해봤는데, 1초에서 4초에 나왔던 map 이 반복되고 있었다.

1초 = 5초 = 9초 = 13초 ...

2초 = 6초 = 10초 = 14초 ...

3초 = 7초 =11초 = 15초 ...

4초 = 8초 = 12초 = 16초 ...

 

여기서, 직접 3초를 어떻게 구해야 할지, 생각해봤다.

폭탄과 인접한 인덱스값을 ' . ' 가 아닌 다른 값을 넣어주는 것이다.

 

입력은 ' . ' 이 아닌, 'O' + 1 인 'P' 값을 주는것이다. ( 'P'를 고른이유는 딱히 없다. 단순히 +1 한 값이다.)

이렇게 한다면, 루프에서 3초 그룹에 해당하는 map 은 폭탄('O')과 인접폭탄('P') 을 제외한 빈공간(' . ') 이 폭탄으로 표기되면 된다.

 

자, 완료했다는 생각에 제출하기를 누르는 순간, 17% 까지 오르다가 '틀렸습니다.' 를 확인할 수 있었다.

아무리 생각해도 왜일까..? 

예제입력들 모두 정상적으로 출력하는데 왜일까? 고민했다.

사실 약 8개월만에 알고리즘문제를 풀어봤기에 문제푸는 감각을 잊었던게 컸다.

 

예제로 준 테스트 케이스는 믿지 않기.

 

3 4 5 

OXXX

XXOX

OXXX

 

이 테스트 케이스를 진행해보았다.

time(N)	1	2	3	4	5
map[][]	OXXX XXOX OXXX	OOOO OOOO OOOO	XXXO XXXX XXXO	OOOO OOOO OOOO	OOXX OOOX OOXX

1초와 5초가 다른것을 확인할 수 있었다.

 

그래서 6초 7초 8초 까지 반복해본 결과,

1초

3초 = 7초 = 11초 ...

5초 = 9초 = 13초 ...

이런 규칙이었다.

 

따라서 코드를 수정했고, 다시 제출한 결과 '맞았습니다'를 확인할 수 있었다.

 

아래는 내가 작성한 코드이다.

 

아래 코드는 int 형 배열로 진행되었고, 0 을 빈곳, 1을 폭탄, 2를 인접한 곳 으로 맵핑해두었다.

 

#include <stdio.h>
#define MAX 200

int map[MAX+1][MAX+1];

bool isOutOfBounds(int x, int y, int R , int C);
void solution(int R, int C, int N);

int main(int argc, char const *argv[])
{
    int R, C, N;
    char c;
    int i, j;
    scanf("%d %d %d", &R, &C, &N);
    getchar();
    for(i = 0; i < R; i++) {
        for(j = 0; j < C; j++) {
            c = getchar();
            if(c == 'O') {
                map[i][j] = 1;
                if(!isOutOfBounds(i-1, j, R, C) && map[i-1][j] == 0) map[i-1][j] = 2;
                if(!isOutOfBounds(i+1, j, R, C) && map[i+1][j] == 0) map[i+1][j] = 2;
                if(!isOutOfBounds(i, j-1, R, C) && map[i][j-1] == 0) map[i][j-1] = 2;
                if(!isOutOfBounds(i, j+1, R, C) && map[i][j+1] == 0) map[i][j+1] = 2;
            } else if(map[i][j] != 2) map[i][j] = 0;
        }
        getchar(); // 개행
    }

    solution(R, C, N);

    return 0;
}

bool isOutOfBounds(int x, int y, int R , int C) {
    return !(x >= 0 && x < R && y >= 0 && y < C);
}

void solution(int R, int C, int N) {
    int i, j;
    char c;
    // N 이 1인 경우, 예외 케이스이다.
    // N 이 짝수인 경우는 폭탄과 상관없이 항상 폭탄으로 차있어야 한다.
    // N 이 3 이상인경우, N-3 을 4로 나눴을때, 나머지가 있는 경우와 나머지가 없는 경우 두가지 케이스가 존재한다.
    if(N == 1) {
        for(i = 0; i < R; i++) {
            for(j = 0; j < C; j++) {
                c = map[i][j] == 1 ? 'O' : '.'; 
                printf("%c",c);
            }
            printf("\n");
        } 
    }
    
    else {
        // N 이 3이상인 경우, 기존에 map 에서 0 인 값들만 폭탄으로 바꿔준다. 
        for(i = 0; i < R; i++) {
            for(j = 0; j < C; j++) {
                map[i][j] = map[i][j] == 0 ? 1 : 0;
            }
        }
        // 새롭게 만들어진 map 에서 폭탄 (1) 주변 (상,하,좌,우) 폭탄을 인접폭탄 (2) 으로 바꿔준다.
        for(i = 0; i < R; i++) {
            for(j = 0; j < C; j++) {
                if(map[i][j] == 1) {
                    if(!isOutOfBounds(i-1, j, R, C) && map[i-1][j] == 0) map[i-1][j] = 2;
                    if(!isOutOfBounds(i+1, j, R, C) && map[i+1][j] == 0) map[i+1][j] = 2;
                    if(!isOutOfBounds(i, j-1, R, C) && map[i][j-1] == 0) map[i][j-1] = 2;
                    if(!isOutOfBounds(i, j+1, R, C) && map[i][j+1] == 0) map[i][j+1] = 2;
                }
            }
        } 
        // 출력 부분 
        for(i = 0; i < R; i++) {
            for(j = 0; j < C; j++) {
                if(N % 2 == 0) c = 'O';
                else if((N-3) % 4 != 0) c = map[i][j] == 0 ? 'O' : '.'; // 5, 9, 13, ...
                else c = map[i][j] == 1 ? 'O' : '.'; // 3, 7, 11, ...
                printf("%c",c);
            }
            printf("\n");
        } 
    }
}

 

 

사실, 원래 char 형 배열로 진행했었다.(코드 구현방식은 동일 0 을 ' . ', 1 을 'O' , 2 를 'P' 로 변경하여 진행)

 

그런데 동작하지 않는 것이였다. 

꽤나 오랜시간 고민했다가 문득 char형 배열을 전역에 설정하면 어떤값을 가지는지 궁금했다. 

그렇게 확인해보니, 0 에 해당하는 값이 들어가 있어서 동작하지 않았던 것이였다.

 

대부분 int 형 배열을 다뤘고, 0으로 초기화 하기 위해 전역변수에 설정해뒀었는데,

char형 배열또한 0으로 초기화되어 있어, 다시 ' . ' 으로 초기화를 했었어야 했다.

 

 

어려운 문제는 아니였지만, 오늘 이 문제를 풀면서 많이 배웠다.