[백준 16918번] 봄버맨 (python)

문제

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

• 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
• 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
• 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
• 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
• 3과 4를 반복한다.

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

예를 들어, 초기 상태가 아래와 같은 경우를 보자.

...
.O.
...

1초가 지난 후에는 아무 일도 벌어지지 않기 때문에, 위와 같다고 볼 수 있다. 1초가 더 흐른 후에 격자판의 상태는 아래와 같아진다.

OOO
OOO
OOO

1초가 지난 후엔 가운데에 있는 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.

O.O 
... 
O.O

 

기록

(graph 3일차) 그래프 문제처럼 푼건지 잘 모르겠다ㅎㅎ

 

폭탄이 규칙에 맞게 변하기 때문에 규칙을 알아야 한다. 1초가 지난 뒤 까지는 처음 상태 그대로, 짝수 초가 지난 시점에는 폭탄을 다 채워넣기 때문에 모든 칸이 폭탄으로 채워져있다. 그 다음부터 3초가 지나는 시점에는 전체 폭탄에서 처음 폭탄이 터지는 범위 밖의 폭탄만 살아남는다. 다시 폭탄이 채워지고 5초가 지나는 시점에는 두 번째 폭탄이 터지는 범위 밖의 폭탄만 살아남는다.

 

이 과정이 반복되기 때문에 정리해보자면,

처음 ~ 1초가 지난 뒤 -> 처음 상태 그대로

짝수 초가 지난 뒤 -> 모든 칸이 폭탄

3초, 7초, 11초,,, 가 지난 뒤 -> 처음 폭탄이 터지는 범위 밖에 폭탄 위치함

5초, 9초, 13초,,, 가 지난 뒤 -> 두번째 폭탄이 터지는 범위 밖에 폭탄 위치함

따라서 이대로 코드를 구현하면 된다.

 

코드

import sys
input = sys.stdin.readline

r, c, n = map(int, input().split())
board = [list(input().strip()) for i in range(r)]

if n<=1 :
    for li in board : print(''.join(li))
elif n%2==0 :
    for i in range(r): print('O'*c)
else :
    # 첫번째 폭탄이 터진 상태
    bombs1 = [['O']*c for i in range(r)]
    for y in range(r):
        for x in range(c):
            if board[y][x]=='O': bombs1[y][x] = '.'
            else :
                for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    if y+i>=0 and y+i<r and x+j>=0 and x+j<c and board[y+i][x+j]=='O':
                        bombs1[y][x] = '.'
                        break

    # 두번째 폭탄이 터진 상태
    bombs2 = [['O']*c for i in range(r)]
    for y in range(r):
        for x in range(c):
            if bombs1[y][x]=='O' : bombs2[y][x] = '.'
            else :
                for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    if y+i>=0 and y+i<r and x+j>=0 and x+j<c and bombs1[y+i][x+j]=='O':
                        bombs2[y][x] = '.'
                        break

    if n%4==3:
        for li in bombs1 : print(''.join(li))
    if n%4==1:
        for li in bombs2 : print(''.join(li))

1. 변수와 폭탄 정보를 저장한다.

2. n이 1보다 작을 때, 초기 상태를 출력한다.

3. n이 짝수 일 때, 모든 칸을 폭탄으로 출력한다.

4. 위의 경우가 모두 아닐 경우, 첫 번째 폭탄이 터진 상태를 저장하기 위해서는, 전체 칸을 폭탄으로 초기화 시켜놓고 각 칸이 폭탄이거나 상하좌우에 폭탄이 있을 경우 폭탄없음으로 저장한다.

5. 두 번째 폭탄이 터진 상태를 저장하기 위해서는, 전체 칸을 폭탄으로 초기화 시켜놓고 각 칸이 두 번째 폭탄이거나 상하좌우에 두 번째 폭탄이 있을 경우 폭탄 없음으로 저장한다.

6. 3, 7, 11,, 은 4로 나눴을 때 3이 남기 때문에 이 경우 첫번째 폭탄이 터진 상태를 출력하고, 5, 9, 13,, 은 4로 나눴을 때 1이 남기 때문에 이 경우 두번째 폭탄이 터진 상태를 출력한다.