특정 거리의 도시 찾기
📌문제어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이때 특정한 도시 X부터 출발하여 도달할 수 있는 모든 도시 중 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하시오. 📌풀이모든 간선의 비용이 1로 동일할 때는 너비 우선 탐색(BFS) 이용하여 최단 거리 찾음특정한 도시 X를 시작점으로 BFS 수행하여 모든 도시까지의 최단 거리를 계산한 후 그 값이 K인 경우에 해당 도시 번호 출력 📌코드from collections import deque# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호n, m, k, x = map(int, input().split())graph = [[] for _ in range(n + 1)]..
코딩테스트
2024. 12. 1. 13:48