https://www.acmicpc.net/problem/16918
16918번: 봄버맨
첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.
www.acmicpc.net
풀이 과정
- 초기에 설치해둔 폭탄의 위치를 저장해 둔다.
- 폭탄이 없는곳에 모두 폭탄을 설치시켜 준다.
- 이 때, 초기에 설치해둔 폭탄과 터지는 시간이 다르기 때문에 폭탄이 없는곳에 폭탄을 설치하면서 위치를 따로 저장해 두어야 한다.
- 직전에 설치한 폭탄이 아닌, 더 이전에 설치해둔 폭탄을 터트린다.
- 이 때, 직전에 설치한 폭탄도 터질 수 있으므로 만약 직전에 설치한 폭탄도 터진다면 직전에 설치한 폭탄 집합에서 해당 폭탄을 제거해 준다.
- 입력받은 시간에 맞추어서 2-3 과정을 반복해 주면 된다.
소스 코드
import sys
input = lambda: sys.stdin.readline().rstrip()
R, C, N = map(int, input().split())
matrix = [list(input()) for _ in range(R)]
boompos = []
for i in range(R):
for j in range(C):
if matrix[i][j] == 'O':
boompos.append([i, j])
def set_boom(matrix):
next_boom = set()
for i in range(R):
for j in range(C):
if matrix[i][j] == '.':
next_boom.add((i, j))
matrix[i][j] = 'O'
return next_boom
def boom(matrix, boompos, next_boom):
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
destroypos = set()
for x, y in boompos:
destroypos.add((x, y))
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx and nx < R and 0 <= ny and ny < C:
destroypos.add((nx, ny))
for x, y in destroypos:
if (x, y) in next_boom:
next_boom.remove((x, y))
matrix[x][y] = '.'
time = 1
while time < N:
next_boom = set_boom(matrix)
time += 1
if time == N:
break
boom(matrix, boompos, next_boom)
boompos = next_boom
time += 1
for m in matrix:
print("".join(m))'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글
| [ 1826 ] [ Greedy ] 연료 채우기 (0) | 2022.01.05 |
|---|---|
| [ 1339 ] [ Greedy ] 단어 수학 (0) | 2022.01.05 |
| [ 17352 ] [ Union-Find ] 여러분의 다리가 되어 드리겠습니다 (0) | 2022.01.03 |
| [ 9440 ] [ Greedy ] 숫자 더하기 (0) | 2022.01.01 |
| [ 17951 ] [ 이분 탐색 ] 흩날리는 시험지 속에서 내 평점이 느껴진거야 (0) | 2021.12.30 |