[구현] 봄버맨(1691)

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

16918번: 봄버맨

 

1. 문제 개요

 

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.

봄버맨은 다음과 같이 행동한다.

• 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
• 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
• 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
• 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
• 3과 4를 반복한다.

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

폭탄이 터질 때까지 남은 시간을 숫자로 배열에 저장하고 폭탄이 없는 공간을 0으로 표시했다.

그 다음 루프를 돌리며 시간에 흐름에 따라 바뀐 상태를 배열에 적용해주었다.

while(N>0){
    fill(); // 봄버맨이 남는 공간에 폭탄을 채운다.
    N-=1; // 1초가 지난 후
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            if(list[i][j]==1) boom(i,j); // 폭탄이 터진다.
            else if(list[i][j] > 1) list[i][j] -= 1; // 폭탄이 터질 때까지 남은 시간을 -1 해준다
        }
    }
}

다음과 같이 일련의 단계들을 순서대로 행하도록 코드를 짰다.

fill() 함수는 봄버맨이 1초동안 빈 공간에 폭탄을 심는 함수이고 boom 함수는 배열의 i,j 번째 공간을 터트려주는 함수이다.

void boom(int i, int j) {
    if(list[i-1][j]!=1) list[i-1][j] = 0;
    if(list[i+1][j]!=1) list[i+1][j] = 0;
    if(list[i][j-1]!=1) list[i][j-1] = 0;
    if(list[i][j+1]!=1) list[i][j+1] = 0;
    list[i][j] = 0;
}

void fill(){
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
            if(list[i][j]==0)
                list[i][j] = 4;
}

몇 가지 주의할 점이 있었는데, 먼저 boom 함수에서는 폭탄이 동시에 터진다고 가정하기 때문에 배열의 값이 1인 공간을 함께 터져야할 폭탄이었기 때문에 패스하도록 했다. 또한 fill()함수가 실행된 다음에 바로 while 문 안에서 1초가 줄어들기 때문에 list[i][j] 값을 3이 아닌 4로 초기화했다.

 

또한, boom 함수에서 인덱스 값이 범위를 벗어날 수 있는 문제는 애초에 가장자리를 사용하지 않음으로서 해결했다.

for(int i=1;i<=R;i++){
    cin >> temp;
    for(int j=0;j<C;j++){
        if(temp[j]=='.') list[i][j+1] = 0;
        else list[i][j+1] = 2;
    }
}

따라서 위와 같이 애초에 인풋을 받을 때부터 행과 열의 인덱스를 1부터 받도록 했고, 배열에 접근할 때도 0이 아닌 1부터 접근해서 사용했다.

 

이렇게 했는데 통과되지 않아 답답했는데 알고보니 배열의 최대 인덱스를 너무 작게 했기 때문이었다.

또한, 폭탄을 표시하는 문자가 0인줄 알았는데 알고보니 O이었다. 항상 복붙해서 사용하는게 정신건강에 좋을 거 같다.

list[201][201] -> list[202][202]로 바꾸고 통과되었다.

 

 

4. 전체 코드

#include<iostream>
#include<string>

using namespace std;

int R, C, N;
int list[202][202];

void boom(int i, int j) {
    if(list[i-1][j]!=1) list[i-1][j] = 0;
    if(list[i+1][j]!=1) list[i+1][j] = 0;
    if(list[i][j-1]!=1) list[i][j-1] = 0;
    if(list[i][j+1]!=1) list[i][j+1] = 0;
    list[i][j] = 0;
}

void fill(){
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
            if(list[i][j]==0)
                list[i][j] = 4;
}

int main(void) {
    cin >> R >> C >> N;
    string temp;
    
    for(int i=1;i<=R;i++){
        cin >> temp;
        for(int j=0;j<C;j++){
            if(temp[j]=='.') list[i][j+1] = 0;
            else list[i][j+1] = 2;
        }
    }
    
    N-=1;
    while(N>0){
        fill();
        N-=1;
        for(int i=1;i<=R;i++){
            for(int j=1;j<=C;j++){
                if(list[i][j]==1) boom(i,j);
                else if(list[i][j] > 1) list[i][j] -= 1;
            }
        }
    }
    
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            if(list[i][j]==0) cout << ".";
            else cout << "O";
        }
        cout << "\n";
    }
}