[boj] 18352_특정 거리의 도시 찾기_python

문제링크

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

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

---

문제설명

문제

 

입력

1 : 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X

2~M+1 :  두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다.

(이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미)

 

출력

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

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

조건

• (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 
•  (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수

---

문제풀이

시작점을  X로 하고, X와의 거리를 distance 배열에 넣는 다익스트라 과정을 거치면

distance[도시 위치] == K인 "도시 위치"를 for문을 이용해 순차적으로 탐색해주면 답을 구할 수 있다.

자세한 풀이는 아래와 같다.

 

# 시간 복잡도 : O(M + MlogM)
# 공간 복잡도 : O(N + M + 1)
# 풀이 시간 : 1h
# 참고 링크 : 이전 나의 최단경로 문제 풀이

import sys, heapq
input = sys.stdin.readline
# 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
# (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)
N, M, K, X = map(int, input().split())
# 최단 거리가 K인 도시가 하나도 없을 때 출력하기 위한 tag 정보
tag = -1

# 그래프 및 거리 정보 저장
graph = [[] for _ in range(N+1)]
distance = [ sys.maxsize for _ in range(N+1)]

# 거리가 1인 A -> B 단방향 그래프 정의
for i in range(M):
    A, B = map(int, input().split())
    graph[A].append([B,1])
# 다익스트라 진행
def dijkstra():
    # 큐에 X에 대한 정보 입력. 자기 자신과의 거리 0, 자기 자신의 좌표 X
    q = []
    heapq.heappush(q, X)
    distance[X] = 0
    # 진행
    while q:
        now = heapq.heappop(q)
        for next, dist in graph[now]:
        	# 현재 비용 계산
            cost = distance[now] + dist
            # 더 적은 값으로 비용 정보 갱신
            if cost < distance[next]:
                distance[next] = cost
                heapq.heappush(q, next)
dijkstra()
# K의 거리를 갖는 것들 출력
for i in range(1, N+1):
    if distance[i] == K:
        print(i)
        tag = i
# 존재하지 않을 시 -1 출력
if tag == -1:
    print(tag)