[Python] 백준 18352번 : 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

---

💡 문제 풀이

그래프 탐색 문제이다.

BFS와 다익스트라 알고리즘 2가지로 해결할 수 있다.

 

출발지점부터 큐에 넣고 가중치를 계산해주면 된다.

✔️ 느낀 점

코드를 짜다보니 어쩌다 보니 BFS로 구현했다.

💻 코드

import sys
from collections import deque
input = sys.stdin.readline
INF = int(10e9)

N, M, K, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    start, end = map(int, input().split())
    graph[start].append(end)

dist = [INF] * (N+1)
dist[X] = 0
q = deque([X])

while q:
    node = q.popleft()
    
    for n in graph[node]:
        if dist[n] == INF:
            dist[n] = min(dist[n], dist[node] + 1)
            q.append(n)
        
if K not in dist:
    print(-1)
    exit(0)

for i in range(1, N+1):
    if dist[i] == K:
        print(i)