[백준] 16918 봄버맨

문제

• RxC 직사각형 격자판의 각 칸은 비어있거나 폭탄이 들어있다.
• 폭탄이 있는 칸은 3초 후 폭발하고, 폭탄이 있던 칸이 파괴되어 빈 칸이 되며 인접한 네 칸도 함께 파괴된다.
• 만약 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발없이 파괴된다. (연쇄 반응 X)
• 1) 처음 일부 칸에 폭탄이 설치되어 있고, 
  2) 2초 후 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 
  3) 1초가 지난 후 3초 전에 설치된 폭탄이 모두 폭발한다.
  4) 2번과 3번을 반복한다.
• N초가 흐른 후 격자판의 상태 구하기

 

• 1 <= R, C, N <= 200
  
  
  

풀이

• 시간이 1초씩 흐른다.
  0초 -> 일부 칸에 폭탄이 설치되어 있는 상태
  1초 -> 움직임 X
  2초 -> 빈 칸에 전부 폭탄 설치
  3초 -> 0초의 폭탄 폭발
  4초 -> 빈 칸에 전부 폭탄 설치
  5초 -> 2초의 폭탄 폭발
  ...
• 즉, 2초부터는 매 초당 (빈 칸에 폭탄 설치 -> 이전 폭탄 폭발 ) 작업이 반복된다.
  2초부터 짝수 초에는 빈 칸에 폭탄을 설치하고, 홀수 초에는 이전에 설치한 폭탄이 폭발하는 작업을 수행한다.

 

• 폭탄 bomb 리스트는 [(이전에 설치한 폭탄의 인덱스), (현재 설치한 폭탄의 인덱스)]로 저장한다.
• blank는 현재 빈 칸의 인덱스를 의미한다.

 

from collections import deque

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

def boom(bomb, blank) :
    visited = set()
    for (x, y) in bomb.pop(0) :
        visited.add((x, y))
        blank.add((x, y))

        for i in range(4) :
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < R and 0 <= ny < C and (nx, ny) not in visited:
                blank.add((nx, ny))
                visited.add((nx, ny))
    bomb[0] -= blank

# 입력 받기
R, C, N = map(int, input().split())
bomb = [set(), ]
blank = set()
for i in range(R) :
    line = list(map(str, input()))
    for j in range(C) :
        if line[j] == 'O' :
            bomb[0].add((i, j))
        else :
            blank.add((i, j))

# N초
for t in range(2, N+1) :  
    if t % 2 == 0 : # 빈 칸에 전부 폭탄 설치
        bomb.append(blank)
        blank = set()
    else :         # 이전에 설치한 폭탄 폭발 
        boom(bomb, blank)
       

# 격자판 출력
for i in range(R) :
    for j in range(C) :
        if (i, j) in blank :
            print('.', end='')
        else:
            print('O', end='')
    print()

 

References

• 백준 그래프 탐색