[백준 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초가 지난 후의 격자판 상태를 출력한다.

 

문제 풀이

import sys
from collections import deque

R,C,N=map(int, sys.stdin.readline().strip().split(' '))
bomber=[list(sys.stdin.readline().strip()) for _ in range(R)]

bomber_queue=deque()
# 초기 상태의 폭탄 위치와 시간 저장
for i in range(R):
    for j in range(C):
        if bomber[i][j]=='O':
            bomber_queue.append((i,j,0))

def install_bomber(time):
    global bomber, bomber_queue
    for i in range(R):
        for j in range(C):
            if bomber[i][j]=='.':
                bomber[i][j]='O'
                bomber_queue.append((i,j,time))

def boom(time):
    global bomber, bomber_queue
    directions=[(0,1),(1,0),(-1,0),(0,-1)]
    # bomber_queue에 요소가 존재하는 경우 조건 추가해야 인덱스 에러 발생하지 않음.
    while bomber_queue and bomber_queue[0][2]==(time-3):
        y,x,t=bomber_queue.popleft()
        bomber[y][x]='.'
        for dy, dx in directions:
            newy=y+dy
            newx=x+dx
            if 0<=newy<R and 0<=newx<C and bomber[newy][newx]=='O':
                bomber[newy][newx]='.'
    # 새로운 bomber queue 업데이트
    new_bomber_queue=deque()
    while bomber_queue:
        y,x,t=bomber_queue.popleft()
        if bomber[y][x]=='O':
            new_bomber_queue.append((y,x,t))

    bomber_queue=new_bomber_queue.copy()

# 처음에 폭탄 설치하고 1초간 아무것도 안함. 2초부터 행동
time=2
while time<=N:
    # 폭탄이 설치되지 않은 칸에 폭탄 설치
    install_bomber(time)
    # 1초가 지난 후 3초 전에 설치된 폭탄 모두 폭발
    time+=1
    if time>N:
        break
    boom(time)
    time+=1

for i in range(R):
    for j in range(C):
        print(bomber[i][j],end='')
    print('')

초기 상태에서 처음 1초간은 아무것도 안하기 때문에 2초부터 폭탄을 설치하는 등의 행동을 하는 것으로 보고, time을 2로 초기화하고 time이 N보다 작거나 같은 동안 while문을 반복하도록 했다.

 

install_bomber(time) 함수에서 전체 bomber를 돌면서 '.'을 가지는 위치에 'O'로 변경해주고, 폭탄의 위치와 해당 폭탄의 설치 시간을 기록하는 bomber_queue에 폭탄의 위치와 현재 시간을 append했다.

 

install_bomber() 함수를 실행하는 동안 시간이 1초 지나기 때문에 time+=1 해준다.

 

이때 +1된 time이 N보다 클 수 있기 때문에 중간 점검 목적으로 if문을 추가해서 time이 N보다 큰 경우 while문을 빠져나온다.

 

boom(time) 함수에서 bomber_queue에서 현재 시간보다 3초 전에 설치된 폭탄들을 popleft 해주면서 해당 위치의 폭탄과 격자판 범위 내의 상하좌우로 인접한 폭탄들을 모두 제거해준다.

*여기서 bomber_queue[0][2]==(time-3)일 때까지만, while문을 반복 ==  현재 시간보다 3초 전의 폭탄이 존재하지 않을 때까지 반복

*또, while 조건에 bomber_queue를 넣어줘서 bomber_queue에 요소가 존재하는 경우에만 탐색하도록 한다. 처음에 이 부분을 생략해서 90%에서 인덱스 에러가 발생했었다.

이후, 기존의 bomber_queue 중에서 제거된 폭탄을 반영하기 위해 큐에 기록된 위치에서 bomber[][]=='O'인 경우에만 new_bomber_queue에 append해주고, 모든 큐를 탐색하고 나면 bomber_queue를 new_bomber_queue로 덮어씌운다. 

 

boom() 함수를 실행하는 동안 시간이 1초 지나기 때문에 time+=1 해준다.

 

time이 N보다 커지면 bomber를 출력하고 종료한다. 

 

다른 풀이를 찾아보니, 폭탄의 위치를 기록한 bomber 2차원 배열과 각 폭탄의 시간을 기록한 time 2차원 배열을 두고, 현재 시간보다 3만틈 작은 시간을 가지는 경우 폭발시키는 풀이법도 있었다! 큐에 모두 저장하고 매번 업데이트하는 것보다 효율적인 방식인 것 같다.