[이것이 코딩 테스트다 with Python] Chapter 13. DFS/BFS - 특정 거리의 도시 찾기

< 특정 거리의 도시 찾기 >

 

💬 문제 설명

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

....

 

입력	출력
4  4  2  1   1  2   1  3   2  3   2  4	4
4  3  2  1   1  2   1  3   1  4	-1

💬 입력 조건

• 첫째 줄에는
  • 도시의 개수 N ( 2 ≤ N ≤ 300,000 ) 
    
  • 도로의 개수 M ( 1 ≤ M ≤ 1,000,000 )
  • 거리의 정보 K ( 1 ≤ K ≤ 300,000 )
  • 도시의 번호 X ( 1 ≤ X ≤ N )
• 둘째 줄부터 M개의 줄에 걸쳐 서로 다른 두 자연수 A B, A에서 B 도시의 단방향 도로를 의미 ( 1 ≤ A, B ≤ N )

💬 출력 조건

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

---

✍ 문제요약

N개의 도시가 있고 각 도시의 도로는 단방향이며 거리는 1이다. 어떤 도시에서 어떤 도시로 도로가 있는지 정보가 주어진다. 이 때, 주어지는 특정 도시에서 최단거리가 K인 도시의 번호를 오름차순으로 출력하여라.

💯 문제링크

백준18352 문제와 동일하다.

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

---

✅  문제 풀이

• 활용 가장 기본적인 BFS 알고리즘을 활용하였다.
• G : 2차원 배열에 인접행렬로 이동할 수 있는 경로를 담았다.
• Vi : 1차원 배열로 한 번 방문한 지점은 방문하지 않도록 했다.
• Q : 에 시작지점을 담아놓고, 이 지점에서 갈 수 있는 지점을 탐색하며 vi에 최단거리를 업데이트 하였다.

from collections import deque

N, M, K, X = map(int,input().split())  # 노드, 간선, 찾고자하는 이동거리, 출발
G = [[] for _ in range(N + 1)]         # 이동경로 표시
vi = [-1] * (N + 1)                    # 방문지점 배열

for _ in range(M):
    u, v = map(int,input().split())     
    G[u].append(v)                     # G에 방문 표시

Q = deque([X])                         # 출발지점 넣고
vi[X] = 0                              # 출발 지점 0으로 

while Q:                               # Q배열이 사라질 때까지
    SP = Q.popleft()                   # 시작지점 뺴고
    for NP in G[SP]:                   # 시작지점에서 갈 수 있는 모든 경로 탐색
        if vi[NP] == -1:               # 방문 안한 지점만
            Q.append(NP)               # 다음 경로로 지정하고
            vi[NP] = vi[SP] + 1        # 방문 표시 하는데 이 전 지점의 경로수에서 + 1

flag = 0
for i in range(len(vi)):               # 방문 표시한 배열 순회
    if vi[i] == K:                     # 해당 위치의 경로가 K라면
        flag += 1                      # flag에 표시
        print(i)                       # 해당 지점의 노드 출력
if not flag : print(-1)                # K지점 없으면 -1