[백준] 봄버맨 [풀이 + 코드 + 문제를 풀며 어떤 생각을 했는가?]

시뮬레이션

https://www.acmicpc.net/problem/16918

16918번: 봄버맨

 

코드

import sys
input = sys.stdin.readline


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


# 상하좌우
dx = [(-1, 0), (1, 0), (0,-1), (0, 1)]

# 초기 폭탄 위치
boomb = [[i, j] for i in range(r) for j in range(c) if arr[i][j] == "O"]
# for i in range(r):
# 	for j in range(c):
# 		if arr[i][j] == "O":
# 			boomb.append([i, j])

time = 0
while time <= n:

	# 0초와 1초는 가만 있으니까
	if time == 0 or time == 1: 
		time += 1
		continue

	if time % 2 == 0:

		arr = [['O' if arr[i][j] == '.' else arr[i][j] for j in range(c)] for i in range(r)]

		# for i in range(r):
		# 	for j in range(c):
		# 		if arr[i][j] == ".":
		# 			arr[i][j] = "O"

	elif time % 2 == 1:
		# 폭탄을 터트려준다.
		# 터트려 주기만 하면되겠네.
		while boomb:
			x, y = boomb.pop()
			arr[x][y] = "."

			for idx in range(4):
				nx = dx[idx][0] + x
				ny = dx[idx][1] + y
				# 범위가 넘어가지 않는 선에서 
				# 인접한 공간은 터트리는데
				# 폭탄이 있는 구역도 터트리게 되고
				if 0<= nx < r and 0 <= ny < c:
					if arr[nx][ny] == "O":
						arr[nx][ny] = "."

		boomb = [[i, j] for i in range(r) for j in range(c) if arr[i][j] == "O"]
		# for i in range(r):
		# 	for j in range(c):
		# 		if arr[i][j] == "O":
		# 			boomb.append([i, j])


	time += 1


for i in arr:
	print("".join(i), end="\n")

 

설명

 이번 문제는 시뮬레이션 유형이라고 생각한다. 문제 조건이 처음에 이해가 잘 가지 않아 힌트에 적혀 있는 예제를 토대로 계산해서 풀어본 문제다. 이 문제를 풀어보고 어떤 논리의 흐름대로 작성을 했는지 알아보려고 한다.

 

 문제의 조건은 N초가 지났을 때 상태를 구하는 문제다. 문제를 읽고 ' N초가 되었을 때 ' 이 말이 가장 어려웠다. 그 이유는 아래 조건들을 보고 다시 생각해 보자.

 

 

• 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
• 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
• 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
• 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
• 3과 4를 반복한다.

 

 

 위 조건을 한번 읽고 나서 ' 다음 1초 '는 도대체 무엇일까 단순 표현인지 정말 무슨 의미가 있는 건지 사실 의미 부여를 해야 할지 말지 결정하는데 참 오래 걸렸던 것 같다. 또한 ' 3초 전 ' 이건 또 어떻게 해석해야 할까.. 특정 초를 지정해서 3초 전이라면 처음 상태를 말하는 것인지 아니면 현재 시점에서 3초 전일지 고민을 많이 했던 것 같다. 때문에 위 조건들만 보고 한 번에 어떻게 구현을 해야 할지 떠올리기 힘들었다. 그래서 가장 마지막 예제를 보고 어떻게 터질지를 고민하며 추론해 본 결과. 3초 전이라는 것은 현재 시점으로부터 3초 전을 의미한다는 것을 알게 되었다. 더 나아가 처음 1번 조건과 2번 조건을 무시해서는 안된다는 걸 알게 되었다. 그 이유는 조건에서는 다음 1초 동안 봄버맨은 아무것도 하지 않는다고 하였다. 따라서 조건을 무시하게 된다면 0초 때와 1초 때는 같은 상태이지만 0초와 1초가 아닌 다른 초일 때를 생각해 보면 답이 다르게 나오는 것을 알 수 있다. 따라서 어떠한 조건이라도 무시하면 안 되지만 명확하게 알 수 있는 건 0초와 1초는 '초기 상태'이다.

따라서 0초와 1초는 변함이 없기 때문에 2초부터 시작하게 되는 걸 알 수 있고 규칙적인 패턴이 존재하게 된다. 그 규칙적인 패턴은 아래와 같다.

 

 

짝수일 때 폭탄을 채운다.

홀수일 때 설치된 폭탄을 터트린다.

 

 

 위 조건을 토대로 어느 시점에 터트려야 하며 채워야 하는지 알 수 있다. 0초와 1초가 지난 시점 즉 2초부터는 짝수시간대이며 이건 어떤 경우에도 동일하다. 시작이 짝수시간부터 시작되니 홀수 시간 때도 3 초부 터인 게 동일하다. 그렇기 때문에 짝수와 홀수시간일 때 어떤 시점에 채우게 되는지 알 수 있고 알게 된다면 터지게 되는 시점도 알게 된다. 홀수일 때 터트리기 때문에 짝수시간에 폭탄을 설치할 곳을 찾아준다. 이때 홀수일 때는 터트리게 되고 그렇게 된다면 다음 시점일 때는 '3초 전에 설치된' 폭탄들이 터질 것이기 때문에' 항상 같은 곳이 터지지 않는다. 모든 공간을 폭탄으로 한번 채우게 되면 이전에 설치된 곳을 터트리게 되는 게 조건이기 때문에 터지고 난 뒤 터진 지점과 상하좌우로 인접한 공간은 모두 빈 공간이 되며 채우게 되는 시점이 돌아왔을 때는 터진 시점에서 터진 이후 터지지 않은 시점이 다음 터지는 시점이 된다. 쉽게 다시 풀어써보면 터지는 시점에서는 인접한 공간들까지도 빈칸으로 만들게 된다. 그럼 모든 폭탄들이 터지게 되면 모든 폭탄들과 연결되어 있는 인접한 공간까지 터지게 된다. 모든 폭탄들이 터지고 난 후 짝수 시간이 되었을 때는 폭탄이 없는 곳을 채우게 되기 때문에 폭탄이 없는 곳에 폭탄을 채운다는 것은 즉 다음 폭탄이 터지는 지점이 된다는 것이다. 왜냐하면 '3초 전에 설치된 폭탄이 모두 폭발한다.'라는 조건 때문이다. 따라서 터지고-채우고-터지고 하는 시점에서 새로 터지는 시점에 대한 3초 전은 이전 3초 전에 터진 시점에서 채워지게 되는 폭탄의 위치가 되게 된다. 이렇게 3번 조건과 4번 조건을 N초가 될 때까지 반복하게 된 이후 N초가 되는 시점까지 시행 후 보드판의 상태를 출력하면 된다.