특정 거리의 도시 찾기 백준 18352번 BFS

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

문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

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

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

모든 문제에서 도로의 거리는 1이다. 다시 말해서 모든 간선의 비용은 1로 고정이 되는데 모든 간선의 비용이 동일할때는 너비 우선 탐색(BFS)를 이용하여 최단 거리를 찾을 수 있다. 다시 말해 모든 도로의 거리는 1이라는 조건 덕분에 BFS로 간단히 해결할 수 있다.

문제의 조건을 살펴보면 노드의 개수 N은 최대 300,000개이며 간선의 개수 M은 최대 1,000,000개이다. 따라서 이 문제는 너비 우선 탐색을 이용하여 시간 복잡도 O(N+M)으로 동작하는 소스 코드를 작성하여 시간 초과없이 해결할 수 있다. 먼저 특정한 도시 X를 시작점으로 BFS를 수행하여 모든 도시까지의 최단 거리를 계산한 뒤에, 각 최단 거리를 하나씩 확인하며 그 값이 K인 경우에 해당 도시의 번호를 추력하면 된다.

#너비 우선 탐색(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)

너비 우선 탐색을 위해서 queue를 사용한다. 그리고 시작지점부터 가장먼저 q에 넣어둔다.

q를 빼내고 여기서 갈 수 있는 곳을 점거을 한다. q에서 빼낸 값을 now에 넣어두고 시작을 하자

next_node는 now에서 갈수 있는 노드를 차례대로 반환할 것이다.

일단 distance를 -1로 초기화해둔 상황이다. 즉 -1과 같다면 방문하지 않은 곳이되니 새로 갱신을 해주자

그리고 q에다가 그 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)

그리고 최단 거리가 k인 모든 도시의 번호를 오름 차순으로 출력을 하게 된다.

그 중에서도 기존의 타겟값이 k가 있다면 이를 출력하고 check를 반환한다.

조건을 만족하지 못하면 print(-1)을 출력

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)

다만 시간초과로 백준에서는 통과가 안된다.