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

💬 문제

문제 난이도: 백준 실버 2

문제 링크: https://www.acmicpc.net/problem/18352

❗️접근 방법

• 시작점이 주어지고, 해당 시작점에서 K만큼 떨어져 있는 도시의 번호를 오름차순으로 출력하는 문제이다.
• K라는 거리가 명확하게 주어졌기 때문에 bfs로 시작점 기준 depth==K일때의 노드가 무엇인지만 알아내면 된다.

✅ 정답 코드(BFS)

# 특정 거리의 도시 찾기
import sys
from collections import deque
input = sys.stdin.readline
print = sys.stdout.write

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

def bfs():
    queue = deque([X])
    visited = [0 for _ in range(N+1)]
    while queue:
        startNode = queue.popleft()
        for nextNode in routes[startNode]:
            if visited[nextNode] == 0:
                visited[nextNode] = visited[startNode] + 1
                queue.append(nextNode)
    flag = True
    for idx, value in enumerate(visited):
        if value == K and idx != X:
            flag = False
            print(f'{idx}\n')
    if flag:
        print('-1')

bfs()

✅ 정답 코드(Dijkstra)

# 특정 거리의 도시 찾기
import sys, heapq
input = sys.stdin.readline
print = sys.stdout.write

N, M, K, X = map(int, input().split(' '))
graph = [[]*(N+1) for _ in range(N+1)]
visited = [sys.maxsize for _ in range(N+1)]
for _ in range(M):
    one, two = map(int, input().split(' '))
    graph[one].append([1, two])

def dijkstra(start):
    H = []
    heapq.heappush(H, [0, start])
    while H:
        d, x = heapq.heappop(H)
        if visited[x] < d:
            continue
        
        for nw, nx in graph[x]:
            nd = d+nw
            if visited[nx] > nd:
                heapq.heappush(H, [nd, nx])
                visited[nx] = nd
    flag = True
    for idx, value in enumerate(visited):
        if value == K and idx != X:
            flag = False
            print(f'{idx}\n')
    if flag:
        print('-1')

dijkstra(X)

✍️ 다익스트라로 풀 이유가 없었던 이유

• bfs로 푼 코드 -> 메모리: 98388kb 시간: 1932ms
• dijkstra로 푼 코드 -> 메모리: 188516kb 시간: 5624ms
• dijkstra는 시작점부터 끝점까지 최소 비용으로 순회해야 하는 경우에 사용하는 알고리즘이다.
• 하지만 위 문제의 경우 경로의 가중치도 없었을 뿐만 아니라(따라서 위에서 가중치는 모두 1로 동일하다)
• 특정 노드로부터 K만큼만 떨어져 있는 도시들의 번호만 알아내면 되는 문제였다.
• dijkstra는 heap을 사용해 heappush와 heappop 모두 O(logN)만큼의 시간 복잡도를 가지지만,
• bfs는 queue를 사용하므로 append, popleft할 때에 O(1)만큼의 시간 복잡도를 가진다는 점에서 이번 문제에 적합하다는 것을 알 수 있다.