백준 16918번 [봄버맨](C++) -yes6686- 티스토리

백준 문제 풀이: 16918번 [봄버맨]

---

문제 링크: https://www.acmicpc.net/problem/16918

문제 설명:

봄버맨은 격자 모양의 맵에 폭탄을 설치하고, 폭탄이 폭발하면서 주변 칸에 영향을 미치는 게임입니다. 문제는 다음과 같은 규칙으로 진행됩니다:

• 초기 상태가 주어지며, '.'은 빈 칸, 'O'는 폭탄이 있는 칸을 의미합니다.
• 1초가 지나면 봄버맨은 아무것도 하지 않습니다.
• 2초가 지나면 모든 빈 칸에 폭탄이 설치됩니다.
• 3초가 지나면 3초 전에 설치된 폭탄이 폭발하여 자신과 인접한 칸을 파괴합니다.
• 이 과정을 주어진 시간 N초까지 반복하여 맵의 상태를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[201][201]; // 격자 상태 저장 배열
int dx[4] = { 0, 0, -1, 1 }; // 상하좌우 이동 배열
int dy[4] = { 1, -1, 0, 0 };

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

    int r, c, n;
    cin >> r >> c >> n;

    // 초기 상태 입력
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == '.') {
                arr[i][j] = -1; // 빈 칸
            } else {
                arr[i][j] = 0; // 폭탄 설치
            }
        }
    }

    n--; // 1초는 초기 상태로 넘어감
    // 폭탄 설치 및 시간 증가
    while (n) {
        n--;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] == -1) {
                    arr[i][j] = 0; // 새 폭탄 설치
                } else {
                    arr[i][j]++; // 기존 폭탄 시간 증가
                }
            }
        }

        if (n == 0) break; // 시간 종료 시 루프 탈출

        n--;
        // 폭탄 폭발 처리
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] != -1) {
                    arr[i][j]++;
                }
            }
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] == 3) { // 폭발 시간 도달
                    arr[i][j] = -1; // 현재 위치 폭발
                    for (int a = 0; a < 4; a++) {
                        int nx = i + dx[a];
                        int ny = j + dy[a];
                        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue; // 범위 초과
                        if (arr[nx][ny] == 3) continue; // 이미 폭발 예정인 칸
                        arr[nx][ny] = -1; // 인접 칸 폭발
                    }
                }
            }
        }
    }

    // 최종 상태 출력
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (arr[i][j] == -1) {
                cout << "."; // 빈 칸
            } else {
                cout << "O"; // 폭탄
            }
        }
        cout << '\n';
    }
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 배열을 사용해 각 칸의 상태를 저장하고 폭탄의 설치, 시간 경과, 폭발 과정을 시뮬레이션합니다.
• 구현 세부사항:
  • 초기화: '.'은 빈 칸(-1), 'O'는 폭탄(0)으로 초기화합니다.
  • 시간 경과 처리: 매 초마다 빈 칸에 폭탄을 설치하고, 기존 폭탄은 시간이 증가합니다.
  • 폭발 처리: 3초가 된 폭탄은 폭발하며 인접한 상하좌우 칸을 모두 파괴합니다.
• 시간 복잡도 분석: 최대 O(R × C × N)입니다. 하지만 N이 4 이상이면 주기적인 상태가 발생하므로 효율적으로 처리됩니다.

---

결과

입력된 맵과 주어진 시간 N초 동안 시뮬레이션을 수행하여 최종 상태를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!