[알고리즘] 16918 봄버맨 - python

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

오랫동안 못풀고 있던 봄버맨을 드디어 풀었다.

go로 했을때 계속 9퍼에서 틀렸다고 나와서 이유를 몰랐는데 파이썬으로 다시 작성하니 통과가 나온다.

그런데 파이썬으로 작성했을때도 Queue 자료형을 쓰다가 계속 시간초과가 나와 이유를 몰랐는데 파이썬에서 Queue 자료형은 다른 스레드가 대기열에 있는 메시지 / 데이터를 사용하여 통신하는 용도로 사용하기 때문에 느려서 그런 것 같다…

찾아보니 리스트를 이용해서 Queue를 구현하거나 deque를 쓰면 된다고 하는데 deque가 리스트를 이용하는 것보다 빠르다고해서 deque로 구현하니 통과하였다.

문제풀이

일정 패턴을 반복하는 맵을 반복하는 문제입니다.

봄버맨은 다음과 같이 행동하는데

초기에 봄버맨은 아무 행동도 하지않고
1초 동안 가만히 있습니다.
그 다음 1초가 지나면 폭탄이 설치되지 않은 모든 칸에 폭탄을 설치합니다.
그리고 3초가 지나 처음에 설치한 폭탄이 터집니다.

그 이후에는 3번과 4번이 계속해서 반복됩니다.

그래서 단순히 1부터 n까지 3번과 4번 행동을 반복하면 되며 폭탄 설치는 1초 간격으로 하기 때문에 i % 2 마다 설치를 해주면 됩니다.

그리고 3번에 폭탄을 설치하기 위해 이전에 설치했던 폭탄의 위치 정보를 담기 위해 큐를 사용하여 폭탄이 설치된 좌표를 미리 기억해 두어야 합니다.

이 과정을 코드로 반복하게 만들면 간단히 해결됩니다.

특정 패턴이 존재하는 것 같아 해당 부분을 찾아 해결하면 더 빠르게 해결될 수 있을 것 같습니다.

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

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
r, c, n = [int(x) for x in input().split()]
bomber = [list(input().rstrip()) for x in range(r)]
dq = deque()
def safe(x, y) :
	return x >= 0 and x < r and y >= 0 and y < c

def bomSet():
	for x in range(r):
		for y in range(c):
			if bomber[x][y] == 'O':
				dq.append((x, y))
			else :
				bomber[x][y] = 'O'

def bomPrint():
	for x in range(r):
		for y in range(c):
			print(bomber[x][y], end="")
		print()

def boom():
	while dq:
		x, y = dq.popleft()
		bomber[x][y] = '.'
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if safe(nx, ny) == True and bomber[nx][ny] == 'O':
				bomber[nx][ny] = '.'
i = 1
while i <= n:
	if i % 2 == 0:
		bomSet()
	else :
		boom()
	i += 1
bomPrint()

yongckim/[알고리즘] 16918 봄버맨 - python