๋ฐ์ํ
๋ฌธ์
ํ์ด
BFS๋ฅผ ์ด์ฉํ์ฌ ํ ์ ์๊ณ , ๊ฐ ๋ฐ์ด๋ฌ์ค๊ฐ ๋ฎ์ ๋ฒํธ๋ถํฐ ์ฆ์ํ๊ธฐ ๋๋ฌธ์ ์ด๊ธฐ์ ํ์ ์์๋ฅผ ์ฝ์ ํ ๋ ๋ฎ์ ๋ฐ์ด๋ฌ์ค์ ๋ฒํธ๋ถํฐ ์ฝ์ ํด์ผ ํ๋ค.
ํ์์ ๋ฎ์ ๋ฐ์ด๋ฌ์ค ๋ฒํธ๋ถํฐ popํ์ฌ ์ํ์ข์ฐ๋ก ๋ฐ์ด๋ฌ์ค ๋ฒ์์ํค๊ณ , ๋ฒ์๋ ์์น๋ฅผ ๋ค์ ํ์ ๋ฃ๊ณ , ์ํ๋ ์๊ฐ์ด ๋ ๋๊น์ง ๋ฐ๋ณตํ๋ค.
์ฝ๋
from collections import deque
n, k = map(int,input().split())
graph = [] # ์ ์ฒด ๋ณด๋ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ
data = [] # ๋ฐ์ด๋ฌ์ค์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ
for i in range(n):
# ๋ณด๋ ์ ๋ณด๋ฅผ ํ ์ค ๋จ์๋ก ์
๋ ฅ
graph.append(list(map(int, input().split())))
for j in range(n):
# ํด๋น ์์น์ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ๋ ๊ฒฝ์ฐ
if graph[i][j] != 0:
# (๋ฐ์ด๋ฌ์ค ์ข
๋ฅ, ์๊ฐ, ์์น x,y) ์ฝ์
data.append((graph[i][j],0,i,j))
# ์ ๋ ฌ ์ดํ์ ํ๋ก ์ฎ๊ธฐ๊ธฐ - ๋ฎ์ ๋ฒํธ์ ๋ฐ์ด๋ฌ์ค๊ฐ ๋จผ์ ์ฆ์ํ๋๊น
data.sort()
q = deque(data)
target_s, target_x, target_y = map(int, input().split()) # ์๊ฐ, ์์น x,y
# ๋ฐ์ด๋ฌ์ค๊ฐ ํผ์ ธ๋๊ฐ ์ ์๋ 4๊ฐ์ง ์์น
dx = [-1,0,1,0]
dy = [0,1,0,-1]
# BFS ์งํ
while q:
virus,s,x,y = q.popleft()
# ์ ํํ s์ด๊ฐ ์ง๋๊ฑฐ๋, ํ๊ฐ ๋น ๋๊น์ง ๋ฐ๋ณต
if s==target_s :
break
# ํ์ฌ ๋
ธ๋์์ 4๊ฐ์ง ์์น๋ฅผ ๊ฐ๊ฐ ํ์ธ
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx>=0 and nx<n and ny>=0 and ny<n:
# ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์์น๋ผ๋ฉด, ๊ทธ ์์น์ ๋ฐ์ด๋ฌ์ค ๋ฃ๊ธฐ
if graph[nx][ny] ==0:
graph[nx][ny] = virus
q.append((virus,s+1,nx,ny))
print(graph[target_x-1][target_y-1])
๋ฐ์ํ
'๐ป Programming > ์๊ณ ๋ฆฌ์ฆ ํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[python] ํ๋ก๊ทธ๋๋จธ์ค_๋จ์ด๋ณํ (DFS&BFS) (0) | 2022.02.06 |
---|---|
[python] ํ๋ก๊ทธ๋๋จธ์ค_๋คํธ์ํฌ (DFS&BFS) (0) | 2022.02.06 |
[python] ๋ฐฑ์ค18352_ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ (DFS&BFS) (0) | 2022.02.06 |
[python] ๋ฐฑ์ค14502_์ฐ๊ตฌ์ (DFS&BFS) (0) | 2022.02.06 |
[ํ๋ก๊ทธ๋๋จธ์ค] 'ํ์ด์ฌ์ ํ์ด์ฌ๋ต๊ฒ' ๊ฐ์ ์ ๋ฆฌ (0) | 2021.08.03 |