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

코드 1 (BFS 이용)

import sys
from collections import deque
input = sys.stdin.readline
n,m,k,x = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1) # 방문 기록용
for _ in range(m):
  s,e = map(int,input().split())
  graph[s].append(e) # 단방향 그래프
  

def bfs(start):
  queue = deque([start])
  visited[start] = 1
  while queue:
    num = queue.popleft()
    for i in graph[num]:
      if not visited[i]:
        visited[i] = visited[num]+1 # 그 이전 방문 값 + 1
        queue.append(i)
bfs(x)
res = []
for i in range(1,n+1):
  if visited[i] == k+1: res.append(i) # 1부터 시작했으므로 k+1 값을 찾아주어야 함
print(-1) if not len(res) else print(*res, sep='\n')

코드 2 (다익스트라 알고리즘 이용)

import sys
from heapq import heappop, heappush
input = sys.stdin.readline
INF = 987654321
n,m,k,x = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [INF]*(n+1)
for _ in range(m):
  s,e = map(int,input().split())
  graph[s].append((e,1)) # 이동 비용은 1

def dijkstra(start):
  queue = [(0, start)]
  visited[start] = 0
  while queue:
    now, next = heappop(queue)
    if now > visited[next]: continue # 현재 값이 더 크면 탐색할 필요가 없다
    for i in graph[next]:
      cost = now + i[1]
      if visited[i[0]]>cost:
        visited[i[0]] = cost
        heappush(queue, (cost, i[0]))

dijkstra(x)
res = []
for i in range(1,n+1):
  if visited[i] == k: res.append(i)
print(-1) if not len(res) else print(*res, sep='\n')