문제 링크

문제 해설

Idea

  • Simulation (or BFS)
  • 초기에 빈 칸(.)을 0, 폭탄이 있는 칸(O)을 1로 설정
  • 처음에 폭탄이 있는 칸의 상태를 우선 1 증가시키고, 이후 모든 칸의 상태를 1씩 증가시키는 과정 반복
  • 매번 각 칸의 상태를 점검하면서 3을 초과할 경우 해당 위치 및 이웃 위치를 폭발 대상에 추가
  • 폭발 대상이 존재할 경우 격자의 범위를 벗어나지 않는 범위 내에서 상태를 0으로 변환
  • 위 과정을 N초 동안 반복하고, 0은 빈칸으로, 나머지는 O로 표시하여 출력

Time Complexity

  • Simulation: O(N^3) = 8,000,000

Data Size

  • R, C, N: 1 <= int <= 200

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import sys
input = sys.stdin.readline

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

board = list()
char2id = lambda x: 0 if x == '.' else 1
id2char = lambda x: '.' if x == 0 else 'O'
for _ in range(R):
    board.append(list(map(char2id, input().strip())))

board = [[state+1 if state > 0 else 0 for state in row] for row in board]

for s in range(2,N+1):
    board = [[state+1 for state in row] for row in board]

    bomb = set()
    for i in range(R):
        for j in range(C):
            if board[i][j] > 3:
                neighbor = [(0,0),(1,0),(-1,0),(0,1),(0,-1)]
                [bomb.add((i+dy,j+dx)) for dy,dx in neighbor]

    for i,j in bomb:
        if 0 <= i < R and 0 <= j < C:
            board[i][j] = 0

for row in board:
    print(''.join(list(map(id2char, row))))