문제
접근
BFS이자, 시뮬레이션 문제이다.
상온에 접촉하는 공기와 접촉하지 않는 공기를 나눠서 구분해줘야 하기 때문에, 치즈로 접근하면 문제가 복잡해진다.
공기를 구분해주기 위해 BFS를 수행하고, 치즈에 대해서 다시 BFS를 수행해야 하므로 일을 두 번하는 느낌이다.
문제 조건 중 테두리는 항상 공기가 입력된다고 했으므로, (0,0)에는 항상 상온인 공기가 존재한다.
(0, 0)에서 BFS를 수행하면 상온인 공기들을 모두 만날 수 있다.
이를 통해 상온인 공기를 찾으며 상온인 공기와 접촉하는 치즈들을 모두 찾아줄 수 있다.
상온과 접촉할 때마다 치즈 값에 +1씩 해준다면 두 변 이상 접촉하고 있는 치즈는 3이상이 될 것이다.
상온과 만난 치즈들을 따로 담아두었다가, 이를 확인하며 3이상인 치즈는 상온으로 변경하고, 3미만인 치즈에 대해서는 다시 1로 바꾸고 앞의 과정을 반복한다.
코드
- 파이썬 코드
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split(' '))
board = []
for _ in range(h):
board.append(list(map(int, input().split(' '))))
def bfs(sx, sy):
dx = [0,0,1,-1]
dy = [1,-1,0,0]
q = deque()
q.append((sx,sy))
visited = [[0]*w for _ in range(h)]
visited[sy][sx] = 1
cheezeQ = set()
while q:
nowx, nowy = q.popleft()
for x, y in zip(dx, dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= w or ny < 0 or ny >= h:
continue
if visited[ny][nx] == 0:
if board[ny][nx] == 0:
visited[ny][nx] = 1
q.append((nx,ny))
if board[ny][nx] > 0:
board[ny][nx] += 1
cheezeQ.add((nx,ny))
return cheezeQ
def cheezeCheck(q):
flag = True
for x, y in q:
if board[y][x] >= 3:
board[y][x] = 0
flag = False
elif board[y][x] == 2:
board[y][x] = 1
return flag
ans = 0
while True:
cheezeQ = bfs(0,0)
if not cheezeQ:
break
flag = cheezeCheck(cheezeQ)
ans += 1
if flag:
break
print(ans)