[DFS/BFS] (1) 특정 거리의 도시 찾기

이코테 p.339 특정 거리의 도시 찾기

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

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

BFS 버전 소스코드

• 현재 노드 now와 연결된 다른 노드에 도달할 수 있으면 '현재 노드까지의 거리 + 1'
• 큐를 이용하여 BFS 구현

from collections import deque
import sys
input = sys.stdin.readline

# 입력받기
n, m, k, x = map(int, input().split())

# 그래프 정보 입력 받기
graph = [[] for _ in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)

distance = [-1] * (n + 1) # 시작 노드에서 다른 모든 노드로의 최단 거리를 저장하기 위한 리스트
distance[x] = 0 # 자기 자신까지의 최단 거리는 0

# BFS 알고리즘
def bfs(x):
  q = deque()
  q.append(x)

  while q: # 큐가 빌 때까지 반복
    now = q.popleft()
    for i in graph[now]: # 현재 노드와 연결된 모든 노드에 대하여
      if distance[i] == -1: # 도달한 적 없는 노드인 경우
        distance[i] = distance[now] + 1
        q.append(i)

bfs(x) # BFS 수행

result = [] # 최단거리가 k인 노드를 저장하기 위한 리스트
for i in range(1, n + 1):
  if distance[i] == k: # 최단거리가 k인 경우
    result.append(i)

result.sort() # 오름차순 정렬

if len(result) == 0: # 최단거리가 k인 노드가 없는 경우
  print(-1)
else:
  for i in result: # 최단 거리가 k인 노드 출력
    print(i)

다익스트라 버전 소스코드

• 다익스트라 알고리즘을 이용하여 시작 노드 x에서 다른 모든 노드까지의 최단거리를 구함

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 표현하기 위함

# 입력받기
n, m, k, x = map(int, input().split())

# 그래프 정보 입력 받기
graph = [[] for _ in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append((b, 1)) # a번 노드에서 b번 노드로 갈 수 있으며, 이 때 비용은 1임을 의미

# 출발 노드 x에서 다른 모든 노드로의 거리 리스트
distance = [INF] * (n + 1)

# 다익스트라 최단 경로 알고리즘
def dijkstra(x):
  q = [] # 우선순위 큐
  heapq.heappush(q, (0, x)) # (거리, 노드 번호) 형태로 큐에 삽입
  distance[x] = 0 # 자기 자신까지의 거리는 0

  # 큐가 빌 때까지 반복
  while q:
    dist, now = heapq.heappop(q) # 큐에서 최상단 노드(= 거리가 최소인 노드) 꺼내기
    for i in graph[now]: # now 노드와 연결된 모든 노드에 대해
      cost = dist + i[1] # 현재 노드를 들렀다 갈 때의 거리
      if cost < distance[i[0]]:
        distance[i[0]] = cost # i[0]번까지의 거리 값 갱신
        heapq.heappush(q, (cost, i[0])) # 큐에 삽입

# 다익스트라 수행
dijkstra(x)

result = [] # 최단 거리가 k인 노드를 저장하기 위한 리스트
for i in range(1, n + 1):
  if distance[i] == k:
    result.append(i)

result.sort() # 오름차순 정렬
if len(result) == 0: # 최단 거리가 k인 노드가 존재하지 않는 경우
  print(-1)
else:
  for i in result: # 최단 거리가 k인 노드의 번호 출력
    print(i)