import sys
import copy
from collections import deque
# ์์ ์
๋ ฅ
N = int(input())
_map = [[0]*N for _ in range(N)]
checked = [[False]*N for _ in range(N)]
queue = deque([])
for i in range(N):
info = list(map(int,sys.stdin.readline().split()))
for j in range(N):
_map[i][j]=info[j]
if info[j] == 9:
_map[i][j] = 0
shark = [i,j,0]
queue.append(shark)
# bfs()๋ก ๋จน์ ์ ์๋ ๋จน์ด ํ์ํ๊ธฐ
dr = [1,-1,0,0]
dc = [0,0,1,-1]
fish = []
def bfs(sharkSize):
copiedMap = copy.deepcopy(_map)
copiedCheck = copy.deepcopy(checked)
while len(queue) !=0:
r,c,t = map(int,queue.popleft())
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
nt = t + 1
if 0<=nr<N and 0<=nc<N and copiedMap[nr][nc]<=sharkSize and not copiedCheck[nr][nc]:
queue.append([nr,nc,nt])
copiedCheck[nr][nc]=True
if 0< copiedMap[nr][nc] <sharkSize:
fish.append([nr,nc,nt])
if fish:
fish.sort(key = lambda x : (x[2],x[0],x[1]))
return fish[0]
else:
return None
sharkSize = 2
food = 0
ans = 0
while True:
fish.clear()
result = bfs(sharkSize)
if result:
r,c,t = map(int,result)
food +=1
if sharkSize == food:
sharkSize+=1
food = 0
_map[r][c]=0
queue.append([r,c,0])
ans+=t
else:
break
print(ans)
์ฝ 2์๊ฐ์ ๊ฑธ์ณ์ ํผ์ ํด๊ฒฐํ ๋ฌธ์ !
๋ฌธ์ ์ ๊ทผ ๋ฐฉ๋ฒ
1. bfs()๋ก ์์ด๊ฐ ๋จน์ ์ ์๋ ๋จน์ด์ ์์น์ ๊ทธ ์์น์ ๋๋ฌํ ์๊ฐ์ ๋ชจ๋ ๊ธฐ๋ก (fish stack์ ์ ๋ ฅ)
2. ๋จน์ด ์ฐ์ ์์์ ๋ฐ๋ผ, ์ ๋ ฅ๋ ๋จน์ด(fish)๋ฅผ ์๊ฐ์์ผ๋ก(=๊ฑฐ๋ฆฌ) ์ค๋ฆ์ฐจ์ ์ ๋ ฌ, ํ์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ, ์ด์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ํ ์ฒซ๋ฒ์งธ์ ์์นํ ๋จน์ด๋ฅผ return ํ๋ค.
๋ง์ฝ, ๋จน์ด๊ฐ ์กด์ฌํ์ง ์๋๋ค๋ฉด None ์ return ํ๋ค.
3. bfs() ์ดํ ์ ์์ ์ผ๋ก ๋ฐํ์ด ๋์๋ค๋ฉด, ๋จน์ ๋ฌผ๊ณ ๊ธฐ ์์ ๊ธฐ๋กํ๊ณ ๋ฌผ๊ณ ๊ธฐ ์์ ๋ฐ๋ผ ์์ด ํฌ๊ธฐ๋ ๋ณ๊ฒฝํ๋ค.
๋จน์ด๋ฅผ ๋จน์ ์์น๊ฐ ์์ด ์์น๊ฐ ๋๋ฏ๋ก queue ์ ์ถ๊ฐํ๊ณ bfs()๋ฅผ ๋ค์ ์คํํ๋ค.
๐ก ์ฃผ์์ . bfs()๋ฅผ ํ๊ธฐ ์ ์ fish ์คํ์ ๋น์์ค๋ค.