문제
봄버맨은 크기가 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
OOO1초가 지난 후엔 가운데에 있는 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.
O.O
...
O.O입력
첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.
출력
총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.
예제 입출력
접근 및 코드
유형 자체는 그래프, 시뮬레이션, 구현으로 되어있는데, 그냥 단순 시뮬레이션 문제가 아니였나 싶다
푼 방식은 단순하다.
주어진 폭탄과 빈칸이 놓여있는 모양을 입력받아서 2차원 배열로 나타내주었다.
몇초 뒤에 폭탄이 터지기 때문에, 폭탄이 놓여진지 몇초가 지났는지 표시할 2차원 배열을 하나 더 만들어 주었다.
폭탄은 0, 빈칸을 -1로 표기했다.
단, 문제에서 처음 1초간은 아무것도 안한다 했기 때문에, 봄버맨이 아무것도 안한채로 시간이 1초 흘렀다고 생각해서, 초기에 입력받는 폭탄위치의 값은, 0이 아닌 1로 표현했다.
폭탄의 경우 상하좌우로 터지기 때문에 다음과 같이 정의했다.
dx = [0,0,-1,1]
dy = [-1,1,0,0]
이는 2차원 배열에서 이동하는 일종의 테크닉이므로 알아두면 좋다.
이제 폭탄이 놓여진지 몇초가 지났는지를, 반복문을 매번 반복할때마다, 1초가 지났다고 생각하고, 매 반복마다, 시간을 체크해둔 2차원 배열의 모든 값을 1씩 증가시킨다.
이때 왜 빈칸을 -1로 두었는지 알 수 있다.
빈칸(-1)에서 1초가 지나면 +1이 되어서 0이 되는데, 0은 폭탄이 놓였음을 의미한다.
그래서 빈칸을 -1로 표현한것이다.
이렇게 모든 값들을 1씩 증가시킬때, 폭탄이 3초뒤에 터진다고 했으니, 3인 값들을 따로 리스트에 저장해주었다.
모든 값을 증가시켰고, 3초가 지난 폭탄의 좌표를 알았으면, 이제 또 반복문을 돌면서, 폭탄을 상하좌우로 터트려주면 된다.
이 과정들이 끝나면 count+1을 해서 시간이 1초 흘렀음을 나타낸다.
코드는 다음과 같다.
import sys
r,c,n = map(int,sys.stdin.readline().split())
#빈칸은 -1로 표기, 초기값을 -1로 표기하고 반복문을 돌면서 입력값에서 폭탄을 찾아서 1로 바꿔준다(원래 0인데, 문제에서 처음에는 1초간 아무것도 안한다해서 1로 만듦)
graph = [[-1 for _ in range(c)] for _ in range(r)]
#몇초가 흘렀는지 세는 변수(시작1초간 아무것도 안하기 때문에 1초부터 시작)
count = 1
#격자판 채우기
for i in range(r):
#한줄을 받음
temp = sys.stdin.readline()
for j in range(c):
if temp[j] == "O":
graph[i][j] = 1
#폭탄을 터트릴 상하좌우 좌표정의
dx = [0,0,-1,1]
dy = [-1,1,0,0]
while count<n:
#1씩 증가시키면서 3인 값의 좌표를 저장해둠
temp_list = list()
#우선 모든 값을 1씩 증가시킴
for i in range(r):
for j in range(c):
graph[i][j]+=1
if graph[i][j] == 3:
temp_list.append([i,j])
#이중에서 3인 값을 찾아서
for a,b in temp_list:
graph[a][b] = -1
#상하좌우 전부 -1로 만듦
for k in range(4):
next_a,next_b = a+dx[k],b+dy[k]
if next_a >= 0 and next_a < r and next_b >=0 and next_b<c:
graph[next_a][next_b] = -1
count+=1
# 결과 출력용 리스트
result = list()
#최종 그래프를 주어진 문제에 맞게 O, . 으로 바꿈
#바꾸면서 행은 문자열로 만들어서 결과 리스트에 넣음
for i in range(r):
temp = ""
for j in range(c):
#-1이면 빈칸
if graph[i][j] == -1:
temp += "."
else:
temp += "O"
result.append(temp)
for i in result:
print(i)결과
유형에 BFS라서 처음에는 각 폭탄이 놓인 상태 자체를 노드로 생각해서 그래프로 풀려고 했지만, 그럴필요 없이 그냥 주어진대로 구현해주면 되는 문제였다.
