[백준][BFS] 16918. 봄버맨

16918. 봄버맨

16918번: 봄버맨

 

• 내 풀이
  • 제대로 생각하고 풀면 어려운 문제도 아닌데....오래도 걸렸다..
  • cnt를 어디서 +1 해주느냐가 중요했던 문제
  • 나는 폭탄이 설치된 곳 주변으로 bfs를 돌면서 터질 곳들 체크하는 방식으로 bfs를 이용

from collections import deque

def zero():
    global cnt
    for i in range(r):
        for j in range(c):
            if graph[i][j]!='O':
                visited[i][j]=cnt
                graph[i][j]='O'
        
def bfs(): #폭탄 설치된 자리와, 함께 터질 인접한 애들 터질 준비
    global cnt
  
    while queue:
        x,y=queue.popleft()
        visited[x][y]=cnt
        
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
        
            if 0<=nx<r and 0<=ny<c and graph[nx][ny]=='.':
                visited[nx][ny]=visited[x][y]
                graph[nx][ny]='O' #zero에서 안터지고 설치될 폭탄과 구별하기 위함
    cnt+=1
    zero() 

def bomb():
    global cnt
    for i in range(r):
        for j in range(c):
            if visited[i][j]==cnt-2:
                graph[i][j]='.'
    

r,c,n=map(int,input().split())
graph=[]
visited=[[0 for _ in range(c)] for _ in range(r)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(r):
    graph.append(list(input().rstrip()))

queue=deque()

cnt=1
while cnt<n:
    for i in range(r):
        for j in range(c):
            if graph[i][j]=='O':
                queue.append((i,j))
      
    bfs()
    if cnt==n:
        break
  
    cnt+=1
    bomb()

#출력
for i in range(r):
    for j in range(c):
        print(graph[i][j], end="")
    print()

 

 

• 다른 사람 풀이
  • n에서 -=1 하는식으로 초 계산
  • 미리 체크해놓을 필요 없이 폭탄이 터질때 bfs를 이용하여 그 주변까지 터트림

import sys
from collections import deque


# 1단계
def loc_bomb():
    for i in range(r):
        for j in range(c):
            if graph[i][j] == 'O':
                bomb.append((i, j))


# 3단계
def full_bomb():
    for i in range(r):
        for j in range(c):
            if graph[i][j] != "O":
                graph[i][j] = "O"


# 4단계
def bombs():
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while bomb:
        a, b = bomb.popleft()
        graph[a][b] = "."

        for i in range(4):
            x = a + dx[i]
            y = b + dy[i]

            if 0 <= x < r and 0 <= y < c:
                if graph[x][y] == "O":
                    graph[x][y] = "."


r, c, n = map(int, sys.stdin.readline().split())
# 1단계: 폭탄을 설치
graph = [list(map(str, sys.stdin.readline().strip())) for _ in range(r)]

# 2단계: 봄버맨은 아무것도 하지 않는다.
n -= 1

while n:
    # 폭탄의 위치를 저장할 리스트
    bomb = deque()

    # 폭탄의 위치 저장
    loc_bomb()

    # 3단계: 모든 칸의 폭탄을 설치
    full_bomb()

    n -= 1
    if n == 0:
        break

    # 4단계: 3초전에 설치된 폭탄 폭발
    bombs()
    n -= 1

for i in graph:
    print("".join(i))