특정 거리의 도시 찾기

📌문제

어떤 나라에는 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)]

# 모든 도로 정보 입력
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

# 모든 도시에 대한 최단 거리 초기화
distance = [-1] * (n + 1)
distance[x] = 0  # 출발 도시까지의 거리는 0으로 설정

# BFS 수행
q = deque([x])
while q:
    now = q.popleft()
    # 현재 도시에서 이동할 수 있는 모든 도시 확인
    for next_node in graph[now]:
        # 아직 방문하지 않은 도시
        if distance[next_node] == -1:
            # 최단 거리 갱신
            distance[next_node] = distance[now] + 1
            q.append(next_node)

# 최단 거리가 K인 모든 도시 번호 오름차순 출력
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check = True

# 만약 최단 거리가 K인 도시가 없다면 -1 출력
if check == False:
    print(-1)

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬