그래프탐색 BFS | BOJ 백준 18352번 특정 거리의 도시 찾기 | Python


created_at : 25 April 2024 - 2 mins read time
Tags: 그래프탐색

Table of Contents


BOJ 백준 18352번 특정 거리의 도시 찾기 | Python

📌 백준 18352번 문제 바로가기

🔎 문제 설명

🩶 실버 2

- 난이도 ★☆☆☆
- 그래프탐색

최단거리를 구하는 방법엔 다양한 알고리즘이 있지만, 난 가장 익숙한 BFS로 풀었다.

이 문제는 최단거리 찾는 유형 중 기본 유형에 속한다. 방문여부를 저장하는 visited 에 거리를 함께 저장했다.


📌 문제 풀이 큰 틀은 다음과 같다.

  • BFS로 가장 가까운 노드부터 최단거리를 계산
  • visited 에 거리를 1씩 더해 첫 도시 - 도시의 거리를 계산



💻 내 코드

# 최단 거리가 정확히 K인 모든 도시들의 번호 출력

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

# N개의 도시, M개의 도로, 출발 도시 X
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)

queue = deque([X])
visited = [-1 for _ in range(N+1)]
visited[X] = 0

# BFS
def bfs():
    while queue:
        now = queue.popleft()
        for node in graph[now]:
            if visited[node] == -1:
                visited[node] = visited[now] + 1
                queue.append(node)
bfs()
if visited.count(K) == 0:
    print(-1)
else:
    for i in range(N+1):
        if visited[i] == K:
            print(i)




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).