[이코테] DFS/BFS 문제 - 특정 거리의 도시 찾기 python

난이도 : ●◐○ | 풀이 시간 : 30분 | 시간 제한 : 2초 | 메모리 제한 : 128MB | 기출 : 핵심 유형

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

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

 

문제

• 어떤 나라에 1~N번까지의 도시와 M개의 단방향 도로가 존재한다.
• 모든 도로의 거리는 1이다.
• 특정한 도시 X로부터 출발해 도달할 수 있는 모든 도시 중 최단 거리가 K인 도시들의 번호를 출력하는 프로그램을 작성하라.

 

입력조건

• 첫째 줄에 도시의 개수 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번 도시로 이동하는 도로가 존재한다는 의미이다.
  • a와 b는 다른 자연수다.

출력조건

• x로부터 출발해 갈 수 있는 도시 중 최단 거리가 k인 도시의 번호를 오름차순으로 한 줄에 하나씩 출력한다.
• 이때 도달할 수 있는 도시 중 최단 거리가 k인 도시가 없으면 -1을 출력한다.

 

입력예시

4 4 2 1
1 2
1 3
2 3
2 4

출력예시

4

 

 

아이디어

• 최단 거리를 저장하기 위한 리스트 distance를 생성한다.
• x번 도시에서 bfs하면서 도시의 거리를 업데이트한다.
• bfs를 수행하고나서 distance에 거리가 k인 도시가 있으면 인덱스를 출력하고 그렇지 않으면 -1을 출력한다.

 

코드

from collections import deque
import sys
input=sys.stdin.readline

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)
def bfs(x):
    q = deque()
    q.append(x)
    distance[x] = 0
    while q:
        now = q.popleft()
        for next in graph[now]:
            if distance[next]==-1:
                distance[next] = distance[now]+1
                q.append(next)

bfs(x)

if k not in distance:
    print(-1)
else:
    for i in range(1,n+1):
        if distance[i]==k:
            print(i)

 

후기

• distance 리스트를 처음엔 다 0으로 초기화시켜두고, 방문여부확인을 위한 visited 리스트를 따로 사용하려고 했었다.
  그런데 distance 리스트를 -1같은 수로 초기화하고
  x가 시작점이니 distance[x] = 0로 업데이트를 해준 뒤에
  bfs를 수행할 때 distnace[?]가 -1이라면 방문하는 방법을 사용하면
  visited라는 리스트를 추가로 사용하지 않아도 된다는 점이 인상깊었다.