[BOJ][⚪1][백준#16918] 봄버맨

문제 출처

BAEKJOON Online Judge #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초가 흐른 후의 격자판 상태를 구하려고 한다. 예를 들어, 초기 상태가 아래와 같은 경우를 보자.

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

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

O.O … O.O

입력

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 ‘.’로, 폭탄은 ‘O’로 주어진다.

출력

총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

예제

예제 1

입력

6 7 3
.......
...O...
....O..
.......
OO.....
OO.....

출력

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

예제 2

입력

6 7 4
.......
...O...
....O..
.......
OO.....
OO.....

출력

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

예제 3

입력

6 7 5
.......
...O...
....O..
.......
OO.....
OO.....

출력

.......
...O...
....O..
.......
OO.....
OO.....

My Sol

def put_bomb():
    global I, J, mat, t
    for i in range(I):
        for j in range(J):
            if not mat[i][j]:
                mat[i][j] = t

def print_mat():
    global I, J, mat
    for i in range(I):
        for j in range(J):
            mat[i][j] = 'O' if mat[i][j] else '.'
    for l in mat:
        print(*l, sep="")

def boom():
    global I, J, mat, t, boom_soon_list

    def boom_one(i, j):
        global I, J, mat
        for di, dj in ((0,0),(-1,0),(1,0),(0,1),(0,-1)):
            si, sj = i+di, j+dj
            if not (0<=si<I and 0<=sj<J): continue
            boom_soon_list.add((si, sj))

    for i in range(I):
        for j in range(J):
            if mat[i][j] == t-3:
                bomb_list.add((i, j))

    while bomb_list:
        bi, bj = bomb_list.pop()
        boom_one(bi, bj)

    while boom_soon_list:
        bi, bj = boom_soon_list.pop()
        mat[bi][bj] = 0

I, J, N = map(int, input().split())
D = {1:2, 2:1}
bomb_list = set()
boom_soon_list = set()
t = -1
mat = []
for _ in range(I):
    lst = list(input())
    mat.append([])
    for k in lst:
        mat[-1].append(0 if k=='.' else -1)

t += 2
if N==1:
    print_mat()
    quit()

put_bomb()
t += 1
if N==2:
    print_mat()
    quit()

while t < N:
    put_bomb() if t%2 else boom()
    t += 1

print_mat()

만만치 않은 구현문제였다.

말 그래도 t를 높여주면서 폭탄을 터트릴 것인지, 폭탄을 심을 것인지 체크하였다. 폭탄이 있는 상하좌우의 좌표를 set으로 모아 중복을 제거한 뒤 한 번에 0으로 제거해주는 것이 필요하다고 느꼈다.

결과

맞았습니다!!

모범답안

출처

R, C, N = map(int, input().split())

if N == 1:
    for _ in range(R):
        print(input())
elif N % 2 == 0:
    for _ in range(R):
        print("O" * C)
else:
    repeat = 2 if N % 4 == 1 else 1
    B = [input() for _ in range(R)]

    for _ in range(repeat):
        result = [["O" for _ in range(C)] for _ in range(R)]
        for i in range(R):
            for j in range(C):
                if B[i][j] != "O":
                    continue
                for ni, nj in (i, j), (i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1):
                    if 0 <= ni < R and 0 <= nj < C:
                        result[ni][nj] = "."
        B = [row[:] for row in result]

    for row in result:
        print("".join(row))

메모리 사용량도, 연산속도도 굉장히 빠른 풀이를 분석해보려 한다.

1. N을 4로 나눈 나머지가 1이면 repeat이 2, 아니면 1
2. 전체를 ‘O’으로 모두 채운 2차원 배열 result로 폭탄을 적용한다.
3. 무슨 이유로 이런 계산이 나온거지?
4. 사실 상하좌우의 공간을 터트리는 ni, nj의 중복이 있을 수 있지만, N이 무수히 커져도 나머지로 반복 자체를 줄여버리니 당연히 시간이 적을 수 밖에 없다.