코딩테스트

[구현, 시뮬레이션] 백준 16918. 봄버맨

말하는 감자에요 2025. 6. 9. 12:33
728x90
반응형

하루에 한 문제씩은 풀었지만, 블로그에 풀이를 올리는 건 정말 오랜만이네요.

 

오늘은 봄버맨 문제를 풀어봤습니다. 시뮬레이션 문제로, 구현만 잘하면 어렵지 않게 해결할 수 있습니다!

 

전 이 문제를 푸는데 4~50분 정도가 걸렸습니다!

 

1. 문제: 백준 16918. 봄버맨

문제

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

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

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

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

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

예를 들어, 초기 상태가 아래와 같은 경우를 보자.

...
.O.
...

1초가 지난 후에는 아무 일도 벌어지지 않기 때문에, 위와 같다고 볼 수 있다. 1초가 더 흐른 후에 격자판의 상태는 아래와 같아진다.

OOO
OOO
OOO

1초가 지난 후엔 가운데에 있는 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.

O.O
...
O.O

입력

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

출력

총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

예제 입력 1

6 7 3
.......
...O...
....O..
.......
OO.....
OO.....

예제 출력 1

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

예제 입력 2

6 7 4
.......
...O...
....O..
.......
OO.....
OO.....

예제 출력 2

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

예제 입력 3

6 7 5
.......
...O...
....O..
.......
OO.....
OO.....

예제 출력 3

.......
...O...
....O..
.......
OO.....
OO.....

2. 문제 풀이

문제를 처음 읽으면 1초 단위로 상태를 계속 시뮬레이션해야 할 것 같지만,

 

폭탄의 패턴이 주기적으로 반복된다는 점에 착안하면 훨씬 쉽게 해결할 수 있습니다!

🔍 핵심 아이디어

  • n == 1: 초기 상태 그대로 출력
  • n 짝수일 때: 무조건 격자 전체가 폭탄 (O)으로 가득 참
  • n 홀수일 때:
    • n % 4 == 3: 한 번 폭탄이 터진 상태
    • n % 4 == 1: 두 번 연속 폭탄이 터진 상태 (n ≥ 5부터 적용됨)

즉, 폭탄이 터진 후의 상태는 주기적으로 반복됩니다.

 

불필요하게 초 단위로 계속 시뮬레이션하지 않아도 됩니다!

구현 코드

def explode(r, c, base_grid):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    new_grid = [['O'] * c for _ in range(r)]
    
    for x in range(r):
        for y in range(c):
            if base_grid[x][y] == 'O':
                new_grid[x][y] = '.'
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < r and 0 <= ny < c:
                        new_grid[nx][ny] = '.'
    
    return new_grid

def simulate(r, c, n, grid):
    # 1. 그대로 출력
    if n == 1:
        return [''.join(row) for row in grid]
     
    # 2. 2초마다 모든 칸에 폭탄 설치
    if n % 2 == 0:
        return ['O' * c for _ in range(r)]
    
    # 3. 폭탄 터지기
    bomb1 = explode(r, c, grid)
    bomb2 = explode(r, c, bomb1)

    return [''.join(row) for row in (bomb1 if n % 4 == 3 else bomb2)]

def main():
    R, C, N = map(int, input().split())
    grid = [list(input().strip()) for _ in range(R)]

    result = simulate(r=R, c=C, n=N, grid=grid)
    for row in result:
        print(row)

if __name__ == '__main__':
    main()

시간 복잡도

  • explode() 함수는 격자 전체를 순회 → O(R * C)
  • 최대 두 번의 explode()만 실행됨
  • 따라서 전체 시간복잡도는 O(R * C) 정도로 매우 효율적입니다.

3. 마무리

이번 문제는 겉보기에는 매 초마다 상태를 갱신해야 할 것처럼 보이지만, 주기성을 파악하면 단 두 번의 폭발 시뮬레이션만으로 해결 가능합니다.

 

문제 속 규칙을 그대로 따라가기보다, 패턴을 파악하고 간소화하는 것이 시뮬레이션 문제의 핵심이라고 느꼈습니다.

 

내일도 꾸준히 한 문제 이상, 화이팅입니다! 💪

 

읽어주셔서 감사합니다.

728x90
반응형