16918_봄버맨
0. 출처
1. 기록
2. 풀이
(1) 아이디어, 시간복잡도, 자료구조
1. 아이디어
>> 3초라는 시간을 채우면 폭발하는게 중요
>> 특정 폭탄이 설치된 곳과 설치된 곳의 시간을 체크하는게 중요
>> 폭탄이 설치되지 않은 다른 곳에 모두 폭탄을 설치해야 됨 (BFS)
>> time_graph
>> bomb_graph
2. 시간복잡도
>> 어떻게 구하는거야?
>> 시간 복잡도 계산하는 법 알아봐야 겠다
3. 자료구조
>> 이차원 배열
>> BFS
(2) 예제 입력, 예제 출력
- 예제 입력 1 - (r, c, n초)
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.....
'''
(3-1) 틀린 풀이
from pprint import pprint
from collections import deque
r, c, n = map(int, input().split())
bomb_graph = [list(map(str, list(input()))) for _ in range(r)]
time_graph = [[0]*c for _ in range(r)]
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
def step1():
for x in range(r):
for y in range(c):
if bomb_graph[x][y] == 'O':
time_graph[x][y] += 1 # 1초 동안 아무것도 하지 않는다.
def step2(): # 폭탄이 설치되지 않은 곳에 폭탄을 설치한다.
for x in range(r):
for y in range(c):
if bomb_graph[x][y] == '.': # 폭탄이 설치되어있지 않은 곳에
bomb_graph[x][y] = 'O' # 폭탄을 설치하고
time_graph[x][y] += 1 # 시간 +1
elif bomb_graph[x][y] == 'O': # 이미 폭탄이 설치되있는 곳에는
time_graph[x][y] += 1 # 시간만 +1
def step3():
for x in range(r):
for y in range(c):
if bomb_graph[x][y] == 'O': # 폭탄이 설치되어 있고
time_graph[x][y] += 1 # 시간을 +1 했을 때
if time_graph[x][y] >= 3: # 시간이 3초이면
bomb_graph[x][y] = '.' # 그 자리에 터뜨리고
for i in range(4): # 4방향을 확인
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<r and 0<=ny<c:
if bomb_graph[nx][ny] == 'O': # 폭탄이 있는 곳이면
bomb_graph[nx][ny] = '.' # 폭탄을 없애고
time_graph[nx][ny] = 0 # 해당 시간을 0으로 초기화
# pprint(bomb_graph)
time = 0
step1()
time += 1
while 1:
if time >= n:
break
else:
step2()
time += 1
if time >= n:
break
else:
step3()
time += 1
for i in range(r):
for j in range(c):
if j == (c-1):
print(bomb_graph[i][j])
else:
print(bomb_graph[i][j], end='')
(3-2) 정답 풀이
from collections import deque
r, c, n = map(int, input().split())
bomb_graph = [list(map(str, list(input()))) for _ in range(r)]
time_graph = [[0]*c for _ in range(r)]
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
def loc_bombs(): # 폭탄 위치 찾아 q 에 저장
for x in range(r):
for y in range(c):
if bomb_graph[x][y] == 'O':
q.append((x, y))
def make_bombs(): # 모든 자리에 폭탄 설치
for x in range(r):
for y in range(c):
if bomb_graph[x][y] == '.':
bomb_graph[x][y] = 'O'
def explode(): # q 에 들어있는 좌표로 폭탄 터트림
while q:
x, y = q.popleft()
bomb_graph[x][y] = '.'
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<r and 0<=ny<c:
bomb_graph[nx][ny] = '.'
n -= 1 # 1초 동안 아무것도 하지 않는다
while n:
q = deque()
loc_bombs()
make_bombs()
n -= 1
if n == 0:
break
explode()
n -= 1
for i in range(r):
for j in range(c):
if j == (c-1):
print(bomb_graph[i][j])
else:
print(bomb_graph[i][j], end='')
3. 참고 및 정리
3초가 된 폭탄은 동시에 터지도록 작성해야합니다.
틀린 풀이로 풀 경우 동시에 설치된 폭탄들이 위치에 따라 연속되어 있는 경우 3초가 되면 선순위에 있는게 먼저 터져 후순위에 있는 폭탄이 사라지게 되는 오류가 발생됩니다. (같은 시기에 설치된 폭탄은 '동시에' 터져야 함)
큐나 덱의 자료구조를 이용해 초기 폭탄 위치를 보관해줌으로서 이러한 문제점을 해결할 수 있습니다.
또한 이러한 자료구조를 이용함으로서 초기 설치한 폭탄과 나중에 설치한 폭탄을 구분지어줄 수 있습니다.
참고한 풀이