[백준] 16918 봄버맨 (python 파이썬)

16918번: 봄버맨

---

 

 

BFS느낌의 구현 문제

---

아이디어

폭탄을 추가하고 터트리는 과정에서 큐를 사용하면 편할 거 같아 deque를 사용했다.

 

1초마다 어떻게 격자판의 변하는지 생각하며 코드를 작성했다.

---

전체 코드

from collections import deque

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
grid = [] # 격자판
boomList = deque() # 폭탄 좌표 리스트

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

for i in range(R): # 격자판 정보 입력
    row = list(input())
    for j in range(C):
        if row[j] == 'O': # 처음 폭탄 좌표들 저장
            boomList.append([i, j])
    grid.append(row)

t = 1 # 처음 1초가 지난 후에 격자판에 아무 일도 벌어지지 않기 때문에, 초기 시간을 1로 잡아도 된다.

while t < N:

    for i in range(R): # 폭탄 채워넣기
        for j in range(C):
            if grid[i][j] == '.':
                grid[i][j] = 'O'

    t += 1
    if t == N:
        break

    while boomList: # 폭탄 터트리기
        x, y = boomList.popleft()
        grid[x][y] = '.'
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                grid[nx][ny] = '.'

    for i in range(R): # 폭탄 터지고 남은 폭탄들 저장
        for j in range(C):
            if grid[i][j] == 'O':
                boomList.append([i, j])

    t += 1

for g in grid:
    print(''.join(g))

---

코드 설명

for i in range(R):
    row = list(input())
    for j in range(C):
        if row[j] == 'O': # 처음 폭탄 좌표들 저장
            boomList.append([i, j])
    grid.append(row)

가장 처음에 있던 폭탄들의 좌표를 boomList에 저장해둔다. 

 

while t < N:

    for i in range(R): # 폭탄 채워넣기
        for j in range(C):
            if grid[i][j] == '.':
                grid[i][j] = 'O'

    t += 1
    if t == N:
        break

    while boomList: # 폭탄 터트리기
        x, y = boomList.popleft()
        grid[x][y] = '.'
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                grid[nx][ny] = '.'

    for i in range(R): # 폭탄 터지고 남은 폭탄들 저장
        for j in range(C):
            if grid[i][j] == 'O':
                boomList.append([i, j])

    t += 1

 

시간이 N초가 될때까지 문제에서 제시한 과정을 반복해 준다. 

1. 빈곳에 폭탄을 채워준다.

2. 1초 경과, 시간이 N초가 되면 break

3. boomList에 있는 폭탄들만 터트려준다. 

4. 폭탄이 터지고, 남아있는 폭탄들만 boomList에 추가해 준다. 

5. 1초 경과.