[boj] 16918_봄버맨_python

문제링크

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

16918번: 봄버맨

---

 

문제설명

입력

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

 

출력

총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

 

조건

1. 폭탄이 있는 칸은 3초가 지난 후에 폭발한다.

2. 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다.

즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다.

3. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다.

따라서, 연쇄 반응은 없다.

4. 봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다.

봄버맨은 다음과 같이 행동한다.

 

0s. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.

1s 다음 1초 동안 봄버맨은 아무것도 하지 않는다.

2s 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.

3s 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.

 

4,6,8,...s : 2s를 반복 

(1+4k)s : 

(3+4k)s : 처음 설치된 부분의 상하좌우가 터진다.

---

문제풀이

Case1 N == 1 # N이 1일 때

0s "가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다."

1s "다음 1초 동안 봄버맨은 아무것도 하지 않는다."

=> 설치한 뒤로 바뀌는 점이 존재하지 않는다.

=> 입력한 값이 그대로 출력된다.

 

Case2. N %2 == 0 # N이 짝수일 때

2,4,6,...s (짝수)초일 때 "폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다."

=> 모든 칸에 'O'가 출력된다. 

 

Case3. N % 4 == 1 ( N ≠ 1) # N이 5이상이고 조건을 만족할 때. 5, 9, 13, ...

5,9,13,... 초일 때 " 처음에 설치되지 않은 곳주변에 있는 칸이 터진다. "

=> 처음 터진곳이 아닌 곳에 폭탄이 채워지고 그 채워진 부분이 터진다.

 

 

Case4. N % 4 == 3 # N이 3이상이고 조건을 만족할 때. 3, 7, 11, 15, ...

3,7,11,... 초일 때 처음 폭탄이 설치된 부분의 상하좌우가 터진다.

=> 처음 설치된 폭탄을 포함한 주변 칸이 '.' 나머지 칸이 'O'이 출력된다.

# 풀이시간 5h
# 시간 복잡도 O(R⁴C⁴) # N % 4 == 1(N > 1)일 때 
# 공간 복잡도 O(RC)
import sys
from collections import deque
input = sys.stdin.readline
R, C, N = map(int, input().split()) # R: 가로, C : 세로, N : 초(sec)
bomberList = [list(input().strip('\n')) for _ in range(R)] # 처음 폭탄 위치
Q = deque()
D = [[0, 1], [0, -1], [-1, 0], [1, 0]] # 폭탄 주변
# N == 1일 때
if N == 1:
    # 그대로 출력
    for i in range(R): print(*bomberList[i], sep="")
# N % 2 == 2일 때
elif N % 2 == 0:
    # 전체를 O로 출력
    for _ in range(R):
        for _ in range(C):
            print("O", end="")
        print()
# N % 4 == 1일 때
elif N % 4 == 1:
	# 처음 폭탄이 있는 좌표를 큐에 넣는다
    for y in range(R):
        for x in range(C):
            if bomberList[y][x] == "O":
                Q.append([y, x])
	# 그 주변부도 폭탄으로 채운다. 
    while Q:
        qy, qx = Q.popleft()
        for dy, dx in D:
            X, Y = qx+dx, qy+dy
            if 0 <= X < C and 0 <= Y < R and bomberList[Y][X] == ".":
                bomberList[Y][X] = "O"
                
    # 해당하지 않는 부분을 큐에 넣는다.
    for y in range(R):
        for x in range(C):
            if bomberList[y][x] == ".":
                Q.append([y, x])
    # 해당하지 않는 부분의 주변부에 폭탄이 존재할 경우 .으로 바꾼다.
    while Q:
        qy, qx = Q.popleft()
        for dy, dx in D:
            X, Y = qx+dx, qy+dy
            if 0 <= X < C and 0 <= Y < R:
                if bomberList[Y][X] == "O":
                    bomberList[Y][X] = "."
    for i in range(R): print(*bomberList[i], sep="")
# N % 4 == 3일 때
elif N % 4 == 3:
    for y in range(R):
        for x in range(C):
        	# 처음 폭탄이 있던 곳을 .으로 만듦
            if bomberList[y][x] == 'O':
                bomberList[y][x] = '.'
                Q.append([y, x])
            else:
                bomberList[y][x] = 'O'
    # 처음 설치된 폭탄을 포함한 주변의 폭탄을 .으로
    # 나머지 부분을 O로 출력
    
    # 처음 폭탄이 있던 주변부를 .으로 만듦
    while Q:
        qy, qx = Q.popleft()
        for dy, dx in D:
            X, Y = qx+dx, qy+dy
            if 0 <= X < C and 0 <= Y < R:
                if bomberList[Y][X] == 'O':
                    bomberList[Y][X] = '.'
    for i in range(R): print(*bomberList[i], sep="")

---

참고 레퍼런스

1. https://yam-cha.tistory.com/187

[백준] 16918. 봄버맨