[ 백준 ] 16918 봄버맨 (python)

 

 

 

 

 

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

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.....

 

 

🔥 문제 풀이

 

이 문제를 풀기 위해서 우선 두 가지 함수로 나눠서 구현하고, 반복문을 돌려서 n과 같아질 때 반복문이 멈추도록 구현해줘야겠다고 생각했다.

 

 

1️⃣ 2초일 때, 빈 공간에 폭탄을 설치하는 함수 (plant 함수)

2️⃣ 3초일 때, 처음 심어뒀던 폭탄을 터트리는 함수 (bomb 함수)

 

 

함수를 실행하기 전에 폭탄은 3초 후에 터지기 때문에 3초 전에 설치된 폭탄의 위치를 따로 기록해 둬야 터트릴 폭탄을 구분할 수 있겠다고 생각해서 queue를 만들어 주어진 폭탄의 위치를 기록해뒀다.

그리고 1️⃣번 함수를 통해 빈칸 모든곳에 폭탄을 설치했고,

2️⃣번 함수에서 queue를 사용해서 BFS를 실행해 좌, 우, 상, 하, 본인을 빈칸인 상태로 만들어줬다.

 

 

이렇게 간단하게 구현하면 문제가 풀릴 것이라 생각했는데 문제 힌트를 보니 격자판이 5번을 기준으로 반복된다는것을 알았다! 그래서 주어진 n을 5로 나눈 나머지값으로 변경해줘서 실행했는데 여기서 에러가 발생했던 것 같다.

아래 코드로 실행을 해봤더니 처음엔 틀렸다고 결과를 받았다.

 

from collections import deque
 
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
 
def plant(arr):
    for i in range(r):
        for j in range(c):
            if arr[i][j] == '.':
                arr[i][j] = 'O'
    
 
def bomb(queue):
 
    while queue:
        x, y = queue.popleft()
 
        if not visited[x][y]:
            visited[x][y] = True
            arr[x][y] = '.'
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
 
            if not visited[nx][ny]:
                visited[nx][ny] = True
                arr[nx][ny] = '.'
 
 
r, c, n = map(int, input().split())
arr = [list(input()) for _ in range(r)]
count = 1
 
if n > 6:
    n %= 5
 
while n != 0:
 
    if count == n:
        break
 
    queue = deque([])
 
    for i in range(r):
        for j in range(c):
            if arr[i][j] == 'O':
                queue.append((i, j))
    
    plant(arr)
    count += 1
 
    if count == n:
        break
 
    visited = [[False] * c for _ in range(r)]
    bomb(queue)
    count += 1
 
 
for i in arr:
    print("".join(i))

 

 

아마도 n = 1일때 처리를 해주지 않아서 에러가 발생하는 것 같았다.

그리고 count == n일때 break 하는 구문이 두 번이나 반복되는 게 좀 걸렸다.. 이러면 안될것같은 느낌..

 

 

그래서 이번엔 count를 따로 만들지 않고, n을 -1씩 줄여가면서 n이 0이 되면 출력할 수 있도록 만들어줬다.

단, n = 1인경우엔 맨 처음 격자판과 똑같기 때문에 n에서 1을 먼저 빼준 후에 while문이 실행되도록 구현했다.

 

이렇게 수정했더니 문제없이 통과😎

 

 

from collections import deque
import sys
 
sys.stdin = open('input.txt')
sys.stdout = open('output.txt','w')
 
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
 
def plant():
    for i in range(r):
        for j in range(c):
            if arr[i][j] == '.':
                arr[i][j] = 'O'
    
 
def bomb():
    while queue:
        x, y = queue.popleft()
 
        if not visited[x][y]:
            visited[x][y] = True
            arr[x][y] = '.'
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
 
            if not visited[nx][ny]:
                visited[nx][ny] = True
                arr[nx][ny] = '.'
 
 
r, c, n = map(int, input().split())
arr = [list(input()) for _ in range(r)]
 
n -= 1 # n = 1인경우엔 아무것도 하지 않기 때문에 제외하기
 
while n:
    queue = deque([])
 
    for i in range(r):
        for j in range(c):
            if arr[i][j] == 'O':
                queue.append((i, j))
    
    plant()
    n -= 1
 
    if n == 0:
        break
 
    visited = [[False] * c for _ in range(r)]
    bomb()
    n -= 1
 
for i in arr:
    print("".join(i))