[이코테] BFS - 특정 거리의 도시 찾기 with 파이썬

1. 문제

• 백준 18352와 동일한 문제
  - 링크

• 1~ N 도시, M개 단방향 도로 존재

• 특정 도시 X에서 출발 , 최단 거리가 정확히 K인 도시들의 번호를 출력하는 프로그램을 작성

• X에서 X로 가는 최단 거리는 항상 0

• 입력

  • N 도시의 개수, M 도로의 개수, 거리 정보 K, 출발도시 번호 X
    • 2 <= N <=300000
    • 1 <= M <= 1000000
    • 1 <= K <= N
  • A B : A에서 B 도시로 이동하는 단방향 도로

• 출력

  • X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한줄에 하나씩 오름차순으로 출력
  • 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력

입출력 예시

2. 아이디어

• BFS를 이용하여, 노드별 최단거리를 리스트로 만들고, 최단거리가 K인지 확인 후 출력한다. K인 리스트가 없다면 -1을 출력한다.

3. 예제코드

## 입력 
N, M, K, X = map(int, input().split())

graph = [[] for _ in range(N+1)]   # 그래프 만들기
distance = [-1]*(N+1)              # 최단 거리 리스트

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)             # 그래프 입력

from collections import deque
def BFS(start):                    # BFS
    q = deque()
    q.append(start)
    distance[start] = 0            # Start -> Start 거리는 0 
    
    while q :
        cur = q.popleft()
        
        for i in graph[cur]:
            if distance[i] == -1:    # 미방문이면, 
                distance[i] = distance[cur] + 1   # 인접노드 거리 = 현재거리 + 1
                q.append(i)
                
BFS(X)   # BFS 실행 
possible = False    
for idx, value in enumerate(distance):
    if value == K:          # 최단거리가 K이면
        print(idx)          # 노드번호 출력 
        possible = True     # 최단거리K에 해당하는 노드가 있는지 확인 
        
if possible == False:       # K에 해당하는 노드 없으면, -1
    print(-1)

4. 배운점

• BFS의 방문여부 확인과 더불어, 최단거리를 업데이트 하는 방법

참고

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