[백준] #16918 봄버맨 (python)

16918번: 봄버맨 (acmicpc.net)

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

 

# Code

from collections import deque
import sys
input = sys.stdin.readline

r,c,n = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(r)]

n=n-1 # 1초 동안 봄버맨은 아무것도 안 함

def search(): # 폭탄을 설치한 위치를 queue에 집어넣음 (bfs 돌리기 위해서)
    for i in range(r):
        for j in range(c):
            if graph[i][j] == 'O':
                queue.append((i,j))

def bombset(): # 처음에 폭탄을 설치한 위치 빼고 나머지에 폭탄 설치
    for i in range(r):
        for j in range(c):
            if graph[i][j] == '.':
                graph[i][j] = 'O'

def bfs():
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while queue:
        x, y = queue.popleft()
        graph[x][y] = '.'

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] == 'O':
                graph[nx][ny] = '.' # 연쇄반응은 없다고 했으므로 queue.append((nx, ny)) 하지 않음
                
while n:
    queue = deque()
    search()
    bombset()
    n-=1
    if n==0:
        break
    bfs()
    n-=1

for bomb in graph:
    print(*bomb, sep = '')
#for i in range(r):
#    for j in range(c):
#        print(graph[i][j], end = '')
#    print()

# Comment

bfs를 이용해서 풀었다. bfs 알고리즘의 경우 그냥 기본적인 상하좌우 이용하는 거라서 어렵지않게 짰는데, 그냥 구현 능력이 좀 떨어지는 것 같다.. ㅋㅋㅋ ㅠㅠ 

코드에 대략적인 설명을 써놨는데 솔직히 저게 다라서..... 딱히 설명할 부분이 없다. 여기서 주의해야할 점은 "연쇄반응이 없다" 는 것이다.  즉, 폭탄 옆에 폭탄이 있을 경우 원래 bfs라면 옆의 폭탄 위치를 queue에 집어넣는 과정이 있었겠지만 여기선 연쇄반응이 없으므로 집어넣어주지 않는다. 그냥 상하좌우 폭탄이 터지고 끝이다.

✏️ 마지막 출력 부분에서 알아두면 좋을 것 같아서 가져왔다. 다른 분 코드를 참고했는데, 밑에 주석 처리한 코드처럼 이중포문을 돌려서 배열을 모두 돌면서 출력할 필요없이 *bomb 이런 형식으로 배열의 원소값만 추출해서 간단하게 출력할 수 있다.

for bomb in graph:
    print(*bomb, sep = '')
#for i in range(r):
#    for j in range(c):
#        print(graph[i][j], end = '')
#    print()

 

나도 앞으로 노션에다가 작성 후 이쁘게 가져와야징...