(Python/🥈2)백준리즘알고 18352번: 특정 거리의 도시 찾기

문제 바로가기 

 

문제:

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

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

입력:

첫째 줄에 도시의 개수 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번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

출력:

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

 

import heapq
import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m, k, x = map(int, sys.stdin.readline().split(" "))

graph = [[] for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, sys.stdin.readline().split(" "))
    # a 좌표에서 b좌표로 모든 가중치는 1이다.
    graph[a].append((b, 1))

# 첫 거리는 모두 최댓값으로 선언
dist = [1e9] * (n + 1)

# 가중치, 시작좌표 (문제에서 x라함)
hq = [(0, x)]
heapq.heapify(hq)

while hq:
    # 현재 가중치, 현재 노드
    cur_w, cur_node = heapq.heappop(hq)
    if dist[cur_node] < cur_w:
        continue
    # 현재 노드랑 연결된거 가져옴
    for next_node, next_w in graph[cur_node]:
        # 거리를 계산해봄
        d = cur_w + next_w
        # 더 짧고 , 1로 돌아오는게 아니면
        if d < dist[next_node] and next_node != 1:
            # 다음 노드로 가는 길 중에 가장 짧다고 판단.
            dist[next_node] = d
            # 다음 노드의 그 다음노드를 찾기위해 hq에 넣음
            heapq.heappush(hq, (d, next_node))

flag = False
for i in range(1, n + 1):
    if dist[i] == k:
        flag = True
        print(i)
if not flag:
    print(-1)

 

 

다익스트라로 풀어줬다.

 

처음보는 에러인 Type에러가 났는데 알고보니 i를 0일때가 문제였다.

 

괜히 if문 하나 더 넣어서 하고 했는데 아니였나 보다.

 

https://windy7271.tistory.com/entry/Python%F0%9F%8F%854%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1753%EB%B2%88-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C

(Python/🏅4)백준 알고리즘 1753번: 최단경로

자세한 설명은 예전에 정리한 이 문제를 보면 될거 같다