[Baekjoon] 18352. 특정 거리의 도시 찾기

🔗 Problem Link

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

---

❔Thinking

• 도시의 개수, 도로의 개수, 출발 도시의 번호가 주어질 때, 최단 거리가 k인 도시를 모두 출력한다.

---

💻Solution

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)]
visited = [False] * (n+1)
result = []
dist = 1

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

q = deque([x])
tmp_cnt = len(q)
while q:
    if tmp_cnt == 0:
        tmp_cnt = len(q)
        dist += 1
    now = q.popleft()
    visited[now] = True
    tmp_cnt -= 1
    for i in graph[now]:
        if visited[i] is False:
            visited[i] = True
            q.append(i)
            if dist == k: 
                result.append(i)
    if dist > k:
        break

if result:
    result.sort()
    for r in result:
        print(r)
else:
    print(-1)

 

2. Dijkstra를 활용한 풀이

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m, k, x = map(int, input().split())
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)
result = []

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append((b, 1))


q = []
heapq.heappush(q, (0, x))
distance[x] = 0
while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
        continue
    if dist == k:
        result.append(now)
    for i in graph[now]:
        cost = dist + i[1]
        if cost < distance[i[0]]:
            distance[i[0]] = cost
            heapq.heappush(q, (cost, i[0]))

if result:
    print('\n'.join(map(str, result)))
else:
    print(-1)

---

🗝️keypoint

1. BFS를 활용할 경우, 거리(dist)를 1씩 증가하면서 거리가 k인 도시들을 result에 담고 BFS를 중단한다.
2. 다익스트라 알고리즘은, 특정 위치에서 다른 모든 위치의 거리를 구하는 알고리즘이다.
3. 입력받는 도로의 개수가 최대 1,000,000개 이므로, input이 아닌 sys.stdin.readline을 이용해야 시간을 줄일 수 있다.