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

💡문제접근

• 최단 거리라는 단어를 보자마자 문제를 BFS 탐색 알고리즘을 이용해서 풀어야겠다고 생각은 했다. 하지만 코드로 옮기는 과정에서 계속 난관을 겪었다.
• 이 DFS/BFS 문제는 양방향이 아니라 단방향이다. 단방향은 방향에 맞춰 2차원 리스트에 저장을 해줘야하므로 주의해야한다.

💡코드(메모리 : 98736KB, 시간 : 1752ms)

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

N, M, K, X = map(int, input().strip().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().strip().split())
    graph[A].append(B)

# 최단거리가 K인 도시가 하나도 존재하지 않으면 그대로 -1을 출력
distance = [-1] * (N + 1)
# 도시 X에서 도시 X로 이동하는 최단거리는 항상 0
distance[X] = 0

def BFS(v):
    li = []
    queue = deque()
    queue.append(v)
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if distance[i] == -1:
                distance[i] = distance[v] + 1
                queue.append(i)
                if distance[i] == K:
                    li.append(i)
    li.sort()
    if len(li) == 0:
        print(-1)
    else:
        for i in li:
            print(i)

BFS(X)

📌 양방향

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().strip().split())
    graph[A].append(B)
    graph[B].append(A)

📌 단방향

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().strip().split())
    graph[A].append(B)

💡소요시간 : 48m