[BFS] 백준 #18352 특정 거리의 도시 찾기 - Python

🗂️ 문제

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

 

💡 접근법

인접 리스트를 통해 그래프를 구현하고, BFS를 사용하여 각각의 도시까지의 최단 거리를 distance 리스트에 저장한다. 현재 노드의 거리 값은 이전 노드의 거리 값 + 1이다.

이후 K와 거리가 같은 도시를 출력하면 된다.

 

😎 내 코드

import sys
from collections import deque

def BFS(v):
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue:
        now_node = queue.popleft()
        for i in graph[now_node]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                distance[i] = distance[now_node] + 1

N, M, K, X = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]  # 인접 리스트
visited = [False] * (N+1)  # 방문 리스트
distance = [0] * (N+1)  # 노드 별 최단 거리 리스트

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)

BFS(X)

if K in distance:
    for i, d in enumerate(distance):
        if d == K:
            print(i)
else:
    print(-1)

 

🧐 배운 점

• BFS는 시작 노드와 가까운 노드를 우선적으로 탐색하므로 최단 거리를 구하는 것에 적합하다.

 

✅ 정답 확인