[백준/실버1] [16918] 봄버맨 - python, Pypy 3

봄버맨

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

16918번: 봄버맨

문제내용 봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다. 폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다. 봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다. 다음 1초 동안 봄버맨은 아무것도 하지 않는다. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다. 3과 4를 반복한다. 폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다. 입력방식 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

---

프로그래밍 순서

1. 입력을 받으면서 설치된 폭탄 좌표를 모두 bombs 리스트에 넣기

2. N초가 만약에 짝수라면 항상 모두 폭탄으로 가득할 것이기 때문에 폭탄으로 꽉찬 리스트 반환

3. N초가 만약에 홀수라면 2~N초 동안 for문을 돌면서 홀수 초일 때 폭탄이 터진다.

  3-1. 홀수 초라면 3초 전에 존재했던 폭탄과 그 주위의 폭탄을 터뜨린다.

    3-1-1. 폭탄을 터뜨리면서 destory라는 set에 상하좌우의 좌표를 넣는다.

  3-2. bombs 리스트의 값은 전체 좌표에서 destory 라는 set을 차집합으로 빼준 값으로 업데이트된다. (왜냐면 그 다음 홀수 초에 터질 폭탄은 전체에서 이번에 터진 폭탄을 제외한 것이기 때문에)

4. for문에서 빠져나왔다면 bombs에 존재하는 좌표만이 폭탄임으로 '.' 으로 이루어진 미로에서 bombs의 좌표들만 폭탄으로 변경하여 반환한다.

---

전체코딩

 

- 코드

# 폭탄을 파괴시키는 함수
def destroy_bomb(bombs, R, C):
    destory = set() # 파괴된 폭탄 리스트
    dy = [0, 0, -1, 1]
    dx = [-1, 1, 0, 0]
    for y, x in bombs:
        destory.add((y, x))
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0 <= ny < R and 0<= nx < C:
                destory.add((ny, nx))
    return destory
 
# 입력
R, C, N = map(int, input().split())
miro = []
bombs = [] # 설치된 폭탄의 좌표
for i in range(R):
    data = input()
    miro.append(data)
    for j in range(C):
        if data[j] == 'O':
            bombs.append([i, j])
 
# N초 동안 격자판 상태 업데이트
all_bomb = [['O' for __ in range(C)]for _ in range(R)] # 모든 것이 폭탄으로 가득한 경우
all_bomb_loc  = set([(i, j)  for i in range(R) for j in range(C)])
if N%2 == 0: 
    # 짝수 초에는 항상 폭탄이 꽉 참
    answer = all_bomb
else:
    for s in range(2, N+1):
        if s%2 == 1: # 3초 전의 설치된 폭탄만 폭발
            # 폭발
            destory = destroy_bomb(bombs, R, C)
            # 현재 설치되어 있는 폭탄 업데이트
            bombs = all_bomb_loc - destory
    answer = [['.' for __ in range(C)]for _ in range(R)]
    for y, x in bombs:
        answer[y][x] = 'O'
 
# 출력
for ele in answer:
    print(''.join(ele))

 

 

 

 

---