[코테 스터디] DFS/BFS, 특정 거리의 도시 찾기

Q15. 특정 거리의 도시 찾기

🐣문제

1~N번까지의 도시와 M개의 단방향 도로가 존재합니다. 모든 도로의 거리는 1입니다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하세요. 또한, 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정합니다.


백준 링크 | https://www.acmicpc.net/problem/18352

🐥풀이

heapq와 거리 테이블을 활용한다.
먼저 거리 테이블은 무한대(int(1e9))로 초기화 한 후, 출발도시와 출발도시의 거리는 0이므로 거리테이블[출발도시] = 0으로 넣어준다. 그리고 heapq에 [0, 출발도시]를 미리 넣어줄 것이다.


그 후 heapq가 빌 때까지 아래의 과정을 반복한다.
1. pop하여 ('거리', '목적 도시') 데이터를 꺼낸다.
2. 거리테이블[목적 도시]의 기존 값이 '거리'보다 작으면 모두 건너뛰고 1로 돌아가 과정을 반복한다.
3. 목적 도시와 연결된 도시들의 거리 값을 업데이트 한다.
: 거리테이블[연결도시]의 기존 값이 '출발도시-목적도시의 거리'+1보다 크면 거리 값을 업데이트 하고, heapq에 거리와 도시 정보를 push 한다. (거리 값 +1인 이유는 출발도시와 목적도시의 거리를 dist라고 하자. 그리고 연결도시는 목적도시와 연결되어있으므로 출발도시에서 목적도시에 도착하여 한 다리 더 건너야 연결도시에 도달할 수 있다. 따라서 출발도시와 연결도시의 거리는 dist+1이다.)


heapq가 비어서 반복문이 끝났으면, 거리 테이블에서 k값의 개수를 찾는다.
k값이 0개가 아니면 개수를 출력하고, 0개이면 -1을 출력한다.

🐓코드

import heapq
import sys
input = sys.stdin.readline

# input
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) # a->b 단방향

distance = [int(1e9)]*(n+1) # 최단거리 테이블
q = []

heapq.heappush(q,[0,x]) # 거리, 출발도시 push
distance[x] = 0 # 출발도시-출발도시 거리 0

while q:
  dist, city = heapq.heappop(q) # 거리, 도시

  # 방문확인
  if distance[city] < dist:
    continue

  # 연결된 도시 거리 값 업데이트
  for road in graph[city]:
    if distance[road] > dist+1:
      distance[road] = dist+1
      heapq.heappush(q,[dist+1, road])


# k 거리가 없으면 -1 출력
if distance.count(k)==0:
  print(-1)
# k 거리의 개수 출력
else:
  for i in range(1,len(distance)):
    if distance[i]==k:
      print(i)

⭐2022.04.12

heapq와 거리테이블 활용법을 기억하자-!