๋ฐ์ํ
๋ฌธ์
ํ์ด
'๋ชจ๋ ๋๋ก์ ๊ฑฐ๋ฆฌ๋ 1'์ด๋ผ๋ ์กฐ๊ฑด ๋๋ถ์ BFS๋ฅผ ์ด์ฉํ์ฌ ํด๊ฒฐํ ์ ์๋ค.
์ฝ๋
from collections import deque
n,m,k,x = map(int,input().split()) # ๋์ ๊ฐ์, ๋๋ก ๊ฐ์, ๊ฑฐ๋ฆฌ ์ ๋ณด, ์ถ๋ฐ ๋์ ๋ฒํธ
graph = [[] for _ in range(n+1)] # ๋์ ๊ฐ์ ๋งํผ graph ๋ฆฌ์คํธ ์์ฑ
for _ in range(m): # ๋๋ก ์ ๋ณด ์
๋ ฅ๋ฐ์์ graph ์ ์ ์ฅ
a, b = map(int,input().split())
graph[a].append(b)
distance = [-1]*(n+1) # ๋ชจ๋ ๊ฑฐ๋ฆฌ๋ -1 ๋ก ์ด๊ธฐํ
distance[x] = 0 # ์ถ๋ฐ ๋์ ๊ฑฐ๋ฆฌ๋ 0
q = deque([x]) # ์ถ๋ฐ ๋์๋ฅผ ํ์ ๋ฃ๊ณ
while q:
now = q.popleft() # ํ์ฌ ๋์ pop ํด์
for next_node in graph[now]: # ํ์ฌ ๋์์์ ์ฐ๊ฒฐ๋ ๋์(๋
ธ๋) ํ์
if distance[next_node] == -1 : # next_node๋ฅผ ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฉด
distance[next_node] = distance[now] + 1 # next_node์ ์ต๋จ๊ฑฐ๋ฆฌ ๊ฐฑ์
q.append(next_node) # ํ์ next_node appendํด์ ๋ฐ๋ณต
check = False
for i in range(1, n+1): # distance๊ฐ k์ธ ๋์ ์์ผ๋ฉด ์ถ๋ ฅ
if distance[i] == k:
print(i)
check = True
if check == False: # distance๊ฐ k์ธ ๋์๊ฐ ํ๋๋ ์์ผ๋ฉด -1 ์ถ๋ ฅ
print(-1)
๋ฐ์ํ
'๐ป Programming > ์๊ณ ๋ฆฌ์ฆ ํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[python] ํ๋ก๊ทธ๋๋จธ์ค_๋คํธ์ํฌ (DFS&BFS) (0) | 2022.02.06 |
---|---|
[python] ๋ฐฑ์ค18405_๊ฒฝ์์ ์ ์ผ (DFS&BFS) (0) | 2022.02.06 |
[python] ๋ฐฑ์ค14502_์ฐ๊ตฌ์ (DFS&BFS) (0) | 2022.02.06 |
[ํ๋ก๊ทธ๋๋จธ์ค] 'ํ์ด์ฌ์ ํ์ด์ฌ๋ต๊ฒ' ๊ฐ์ ์ ๋ฆฌ (0) | 2021.08.03 |
[BFS] ๋ฏธ๋ก ํ์ถ (0) | 2021.05.17 |