백준 16918-봄버맨 (파이썬)

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초가 흐른 후의 격자판 상태를 구하려고 한다.

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

...
.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.....

예제 출력 1

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

예제 입력 2

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

예제 출력 2

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

예제 입력 3

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

예제 출력 3

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

힌트

아래는 시간이 지난 후 예제 격자판의 상태이다.

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

<초기 상태, 1초 후>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

<2초 후>

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

<3초 후>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

<4초 후>

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

<5초 후>

---

정답 코드

import sys
from collections import deque

input = sys.stdin.readline

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

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)


def valid_coord(y, x):
    return 0 <= y <= r - 1 and 0 <= x <= c - 1


# 빈칸에 폭탄 설치
def set_bomb():
    for i in range(r):
        for j in range(c):
            if init[i][j] == '.':
                init[i][j] = 'O'


def explode():
    while prev_bomb:
        y, x = prev_bomb.popleft()
        if y == -1 or x == -1:
            break
        for i in range(4):
            if valid_coord(y + dy[i], x + dx[i]):
                init[y + dy[i]][x + dx[i]] = '.'
        init[y][x] = '.'


prev_bomb = deque()


# 폭탄이 설치된 좌표를 찾아 deque에 저장하는 함수
def find_bomb():
    for i in range(r):
        for j in range(c):
            if init[i][j] == 'O':
                prev_bomb.append((i, j))


# 처음 1초동안은 아무 동작도 하지 않으므로 1을 감소시켜준다.
n -= 1
while n:
    find_bomb()
    set_bomb()
    # 초기 상태에서 1초가 더 지난 다음 빈칸에 폭탄을 설치해야 하므로 시간-1
    # 1초를 더 감소시켰을 때 n==0이 아닌 경우에만 폭탄을 폭발시켜준다.
    n -= 1
    if not n:
        break
    explode()
    # 1초가 지난 후에 폭발하는 설정이므로 시간 - 1
    n -= 1
# 출력
for i in init:
    print(''.join(i)

import sys
from collections import deque

input = sys.stdin.readline

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

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)


def valid_coord(y, x):
    return 0 <= y <= r - 1 and 0 <= x <= c - 1


# 초 수가 짝수일 때 빈칸에 폭탄추가
def bfs_even():
    chk = [[False] * c for _ in range(r)]
    dq = deque([(0, 0)])
    while dq:
        y, x = dq.popleft()
        for i in range(4):
            if valid_coord(y + dy[i], x + dx[i]) \
                    and not chk[y + dy[i]][x + dx[i]]:
                dq.append((y + dy[i], x + dx[i]))
                chk[y + dy[i]][x + dx[i]] = True
                if init[y + dy[i]][x + dx[i]] == '.':
                    prev_bomb.append((y + dy[i], x + dx[i]))
                    init[y + dy[i]][x + dx[i]] = 'O'
    prev_bomb.append((-1, -1))


# 초 수가 홀 수 일 때, 3초 전 설치한 폭탄 터뜨림
def odd():
    while True:
        y, x = prev_bomb.popleft()
        if y == -1 or x == -1:
            break
        for i in range(4):
            if valid_coord(y + dy[i], x + dx[i]):
                init[y + dy[i]][x + dx[i]] = '.'
                expl_coord.append((y + dy[i], x + dx[i]))
        init[y][x] = '.'
        expl_coord.append((y, x))
    # 폭발한 좌표가 그 전에 설치한 폭탄에 좌표와 겹치면 연쇄반응없이 폭탄을 없앰
    for e in expl_coord:
        if e in prev_bomb:
            prev_bomb.remove(e)


# 폭발한 좌표를 저장
expl_coord = []

prev_bomb = deque()

# 초기 폭탄의 좌표 저장
for i in range(r):
    for j in range(c):
        if init[i][j] == 'O':
            prev_bomb.append((i, j))
prev_bomb.append((-1, -1))

for i in range(2, n + 1):
    # 짝수 초일 때 빈칸에 설치
    if not i % 2:
        bfs_even()
    # 홀수 초일 때 터뜨림
    else:
        odd()

#출력
for i in init:
    print(*i)

피드백

정답을 못맞춘 가장 큰 이유는 하나 구현하고 오류 수정하고를 반복하다 보니 기존코드에 땜질하는 식으로 되버려서 같은 기능을 훨씬 간단하고 효율적으로 구현할 수 있음에도 불구하고 복잡한 결과물이 나왔다.

예)폭발한 좌표 리스트에 특정 좌표가 들어있으면 prev_bomb에서 지우는 코드 ->

in연산자 \(O(N) *\) deque의 remove -> \(O(N) = O(N^2) \)

또한 그래프 탐색 문제로 분류돼있다 보니 불필요한 BFS탐색을 고집해서 시간복잡도를 키웠고 for문 + 홀, 짝 구분으로 풀었던 것도 한몫했다.

 

위 문제점들은 정답코드와 같이 for문 대신 while문을 사용하고 특정 이벤트마다 시간을 줄이는 개념으로 접근하면 간단하게 해결 가능하다.

매 반복문마다 폭탄이 설치된 좌표를 구하고 폭탄을 설치하고 폭탄을 터뜨리는 동작을 수행하되 특정조건문을 걸어 일괄적으로 일어나지 않도록 조치해주면 되었던 것

어쨌든 이번 문제를 풀면서 다시한번 확인한 사실은 기능을 덕지덕지 붙이다 이게 맞나?싶으면 다시 짜는게 훨씬 낫다는 점이다.

 

그래도 그 와중에 잘한 점을 꼽아보자.

폭탄이 설치된 좌표를 deque에 삽입하고 폭탄을 터뜨린 때 좌표 하나씩 pop한 점, 길찾기 문제에서 고정적으로 쓰이는 상하좌우 방향값 설정과 이 값을 적용한 좌표가 유효한 좌표인지 확인하는 함수도 따로 작성해 놓은 점도 잘했다고 생각한다.

 

새로 알게된 사실

• python의 deque은 mutable한 시퀀스를 리턴한다. 그렇기 때문에 list와 같이 얕은 복사 방식이 기본적으로 적용된다.
• python의 deque은 삽입/삭제 뿐만 아니라 탐색도 가능하다는 점이다. list클래스의 일부 메소드도 사용가능하다. 하지만 deque로 탐색을 하거나 list메서드를 사용한다? 이게 맞는지 다시 생각해보자 ㅎㅎ.. 참고로 deque은 선입선출 시에만 list보다 유리하므로 이 때를 제외한 나머지 상황에서는 굳이 사용하지 않도록 하자
• 참고 deque과 list의 시간복잡도 차이

출처:https://wellsw.tistory.com/122