[ 백준 ] 16918 / 봄버맨

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
149/228
post-thumbnail

# Appreciation

/*
 * Problem :: 16918 / 봄버맨
 *
 * Kind :: Simulation
 *
 * Insight
 * - max(R)=200, max(C)=200, max(N)=200
 *   폭탄을 설치하고 터지는 것은 O(1) 테니
 *   O(200^3) 이면 시간 제한안에 충분히 구현가능할 것 같다
 *
 * - 사이클은 다음과 같다
 *   + T - State      | b1 b2
 *     0 - Init       |  0
 *     1 - Do Nothing |  1
 *     2 - Set        |  2  0
 *     3 - Bomb(T=0)  |  3  1
 *     4 - Set        |  0  2
 *     5 - Bomb(T=2)  |  1  3
 *     6 - Set        |  2  0
 *     7 - Bomb(T=4)  |  3  1
 *     ...
 *
 * - 사실 어차피 상태는 반복된다
 *   + 3 3 100
 *   .O.
 *   O.O
 *   .O.
 *   라는 입력이 들어왔다고 하자
 *     # T = 0
 *     .O.
 *     O.O
 *     .O.
 *     # T = 1
 *     .O.
 *     O.O
 *     .O.
 *     # T = 2
 *     OOO
 *     OOO
 *     OOO
 *     # T = 3
 *     ...
 *     ...
 *     ...
 *     # T = 4
 *     OOO
 *     OOO
 *     OOO
 *     # T = 5
 *     ...
 *     ...
 *     ...
 *     # T = 6
 *     OOO
 *     OOO
 *     OOO
 *     # T = 7
 *     ...
 *     ...
 *     ...
 *     -> 즉, 상태는 사실상 3가지 경우만 가능하다
 *        1번 상태 - (T = 0, 1)
 *        2번 상태 - (T = 2, 4, 6, 8, ...)
 *        3번 상태 - (T = 3, 5, 7, 9, ...)
 *        여기서 1번 상태와 3번 상태가 같을 수도 있다
 *        (그럼 2가지의 경우만 가능 <= 문제의 예제 입력)
 *
 * Point
 * - 폭탄이 설치된 후 몇 초가 흘렀는지 추적해야 한다
 *   즉, 폭탄의 상태를 기록해야 한다
 *   + 폭탄이 없는 것을 -1 로,
 *     폭탄이 설치된 직후를 0 으로 보자
 *     # 시간이 흐를 때마다 +1 해주며
 *       +3 이 되면 터뜨려 준다
 *
 * - 폭탄을 설치하는데 1초가 걸린다
 *   막 설치된 폭탄은 0초가 흐른 상태이다
 *   + 은근히 헷갈리는 부분...
 *
 * - 예전에 풀었던 코드가 다시 풀었던 코드보다 깔끔하더라?!?
 *   씁쓸...
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int R, C, N;
char board[200][200];
int cnt[200][200];
struct Point { int y, x; };
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};

// Set up : Functions Declaration
bool isValid(int y, int x);
void set();
void bomb();


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> R >> C >> N;
    memset(cnt, -1, sizeof(cnt)); /* 모든 칸을 폭탄 없음으로 초기화 */
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            cin >> board[i][j]; /* 사실상 board 는 이후에 쓰이지 않음
                                 * cin 으로 편하게 받아
                                 * cnt 를 초기화하기 위한 도구로만 사용될 뿐... */
            if (board[i][j] == 'O') {
                cnt[i][j] = 1; /* cnt 초기화시 편의상 설치된 폭탄을 1초 흐른 것으로 간주함
                                * 이로써 Init, Do Nothing 상태를 처리함 */
            }
        }
    }

    // Process
    int T = 1; /* 현재 1초 흐른 상태 */
    if (N > 1) {
        while (true) {
            set(); T++; /* 봄버맨 행동 수칙 3, 폭탄 설치 */
            if (T == N) break; /* 시간 되면 반복을 끝냄 */

            bomb(); T++; /* 봄버맨 행동 수칙 4, 3초 전 설치된 폭탄 폭발 */
            if (T == N) break;  /* 시간 되면 반복을 끝냄 */
        }
    }

    // Control : Output
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            /* 폭탄이 설치되지 않은 곳은 -1 값을 가짐 */
            cout << ((cnt[i][j] == -1) ? '.' : 'O');
        } cout << endl;
    }
}

// Helper Functions
bool isValid(int y, int x)
/* 주어진 좌표가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < R && x >= 0 && x < C;
}

void set()
/* 봄버맨 행동 수칙 3, 폭탄 설치 */
{
    /* 폭탄 없음 : -1
     * 폭탄이 설치된 직후 : 0
     * 1초 흐름 : 1
     * 2초 흐름 : 2
     * 3초 흐름 : 3
     * 이니 그냥 모든 칸을 +1 해주면 됨 */
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            cnt[i][j]++;
        }
    }
}

void bomb()
/* 봄버맨 행동 수칙 4, 3초 전 설치된 폭탄 폭발 */
{
    vector<Point> bombs; /* 폭발할 폭탄위 위치 저장됨 */
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            cnt[i][j]++; /* 모든 칸 +1 해줌으로써 시간의 경과 갱신 */
            if (cnt[i][j] == 3) { /* 폭탄이 설치된 지 3초 흘렀으면 */
                bombs.push_back({i, j}); /* 위치 저장 */
            }
        }
    }

    /* 폭탄 폭발, 자신의 위치 및 인접한 칸의 값을 -1 로 만들어 줌으로써 폭탄 제거 */
    for (Point b : bombs) {
        cnt[b.y][b.x] = -1;
        for (int i=0; i<4; i++) {
            int ay = b.y + dy[i];
            int ax = b.x + dx[i];
            if (isValid(ay, ax)) {
                cnt[ay][ax] = -1;
            }
        }
    }
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글