문제 설명 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 입력 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.
출력 X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다. 이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.
코드
from collections import deque
import sys
city, road, dist, start = map(int, sys.stdin.readline().split())
# 그래프 빌드하기
graph = [[] for _ in range(city+1)]
for _ in range(road):
city1, city2 = map(int, sys.stdin.readline().split())
graph[city1].append(city2) # 단방향 연결
def calculate_dist(start_city, target_dist):
# distance array initialized to -1 (unreachable)
distances = [-1] * (city+1)
distances[start_city] = 0 # 시작 도시까지 거리가 0
# Initialize the queue with the starting city
queue = deque([start_city])
while queue:
current_city = queue.popleft() # 큐에서 현재 확인할 도시 꺼내기
# Explore all connected cities
for next_city in graph[current_city]:
# If this city has not been visited yet
if distances[next_city] == -1:
distances[next_city] = distances[current_city] + 1
queue.append(next_city)
# Find all cities at the given distance
result = [i for i in range(1, city+1) if distances[i] == target_dist]
# Return the result in the specified format
if result:
return result
else:
return [-1]
# Get the result and print it
output = calculate_dist(start,dist)
for city in output:
print(city)
문제 풀이
오늘의 문제는 BFS 알고리즘을 사용해서 풀었다.
BFS를 이용해 효과적인 그래프 탐색이 가능하며 모든 간선의 가중치가 동일할 때 최단 거리를 구하는 데 적합하다.
핵심 로직
그래프 초기화: graph 리스트에 도시와 도로 관계를 저장한다.
거리 초기화: 각 도시에 대한 거리를 초기에 -1로 설정해두고 방문 여부를 차례대로 확인한다.
탐색: 출발 도시에서 시작해서 연결된 도시를 탐색하면서 거리를 계산한다
결과: 주어진 거리 K 에 해당하는 모든 도시를 찾아 한 줄씩 출력한다.
시간 복잡도
BFS 알고리즘의 시간 복잡도는 0(N + M) 이다. 여기서 N = 도시의 개수, M = 도로의 개수 이다.
최악의 경우에도 효율적인 성능을 보장한다.
오늘의 회고
이 코드의 핵심은 BFS를 사용하여 주어진 출발점에서 특정 거리까지의 모든 도시를 탐색하는 것이다.
BFS의 경우, 모든 도로의 거리가 동일할 때 최단 거리를 구하기에 적합하다.
이를 통해서 특정 거리만큼 떨어진 모든 도시를 효과적으로 찾을 수 있다.
문제를 보고 처음에는 지난 번에 풀었던 촌수 계산 문제를 참고해서 풀었는데, 중간 부분이 약간 헷갈렸다.
스스로 완벽하게 풀지는 못하고 검색해보면서 다시 풀긴 했지만, 그래도 예전보다 속도가 빨라진 듯하다.
