[BaekJoon] "DFS/BFS" - 백준 16918번 문제 : 봄버맨

[문제 설명]

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

16918번: 봄버맨

 

봄버맨은 크기가 RxC인 직사각형에서 살고 있음, 각 칸은 비어있거나 폭탄이 들어 있음

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 인접한 네 칸도 (상,하,좌,우)도함께 폭발함

봄버맨은 다음과 같이 행동함

1. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치, 모든 폭탄이 설치된 시간은 같음

2. 다음 1초 동안 봄버맨은 아무것도 하지 않음

3. 다음 1초 동안 폭탄이 설치 되어 있지 안은 모든 칸에 폭탄 설치

4. 1초가 지난 후에 3초전에 설치된 폭탄이 모두 폭발

5. 3과 4를 반복

 

 

N초가 흐른 후의 격자판 상태를 구해야 함

 

[해결 로직]

- 먼저, 초기에 폭탄의 위치를 다 저장해놔야함

- 일단 1초일때는 입력된 그대로 보여줘야함

- 또, 2초 단위일때는 모든 곳에 폭탄이 심어지기 때문에 모든 곳에 폭탄을 심은 채로 보여줘야함

- 그럼 나머지 경우에는? BFS 함수를 실행해야함

- BFS 함수 내에서 네 방향으로 탐색함

- 원래 폭탄 리스트에 저장되어 있더 ㄴ위치를 꺼내서 '.'으로 폭발 표시

- 만약 이미 터져있다면 또는 지도 크기에 벗어나면 탐색 안함, 그렇지 않다면 폭탄 터뜨림 ('.' 표시)

- 다 진행한 후에, 폭탄 있는 자리를 다시 큐에 저장

- 이런식으로 폭탄 위치를 기억하고 터뜨리고 기억하고 터뜨리는 것임

 

[Solution 코드]

from collections import deque
r,c,n = map(int, input().split())

ary = []
bomblst = deque()

for i in range(r):
    ary.append(list(map(str, input())))


## 초기 폭탄 위치 저장
for i in range(r):
    for j in range(c):
        if ary[i][j] == 'O':
            bomblst.append((i,j))
            


def finbomb(ary, bomblst, n):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    #print(newmaps)
    recur_n = int(n // 2)
    for _ in range(recur_n):
        newmaps = [['O' for _ in range(c)] for _ in range(r)]
        while bomblst:

            x,y = bomblst.popleft() ## 폭탄 위치 꺼내기
            newmaps[x][y] = '.' ## 폭탄인 곳은 .으로 표시

            for m in range(len(dx)): ## 네 방향 폭탄 터뜨리기

                cx = x + dx[m]
                cy = y + dy[m]

                if cx < 0 or cx >= r or cy < 0 or cy >= c or newmaps[cx][cy] == '.': ## 이미 터져있다면 그냥 continue, 그리고 지도 크기에 벗어나면 continue
                    continue

                newmaps[cx][cy] = '.' ## 폭탄 터뜨리기

        for a in range(r):
            for b in range(c):
                if newmaps[a][b] == 'O':
                    bomblst.append((a,b))

    return newmaps

if n == 1:
    for i in range(r):
        for j in range(c):
            print(ary[i][j], end="")
        print("")
elif n%2 == 0:
    for i in range(r):
        strm = 'O'*c
        print(strm)
else:
    finmaps = finbomb(ary, bomblst, n)
    for i in range(r):
        for j in range(c):
            print(finmaps[i][j], end="")
        print("")

 

폭탄을 터뜨리고 나서 표시해주는 거를 잘 기억해야함

그리고, 홀/짝 경우의 수 나눠서 하면 틀림