[백준알고리즘/18352번/파이썬] 특정거리의 도시 찾기

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

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

어제 1916번 최소비용 구하기 문제를 풀며, 아직 다익스트라 알고리즘에 대해 이해가 부족하다고 느껴 해당 문제를 찾아서 풀어봤습니다.

 

문제: 도시의 개수, 도로의 개수, 찾고자 하는 거리 정보, 출발 도시의 번호, 그리고 도로의 정보가 주어졌을 때, 거리가 K인 도시를 찾는 문제입니다.

 

풀이 방법: 다익스트라 알고리즘을 활용했습니다.

 

풀이 코드:

 

import sys
import heapq


n,m,k,x = map(int, sys.stdin.readline().rstrip().split())
graph = [[] *(n+1) for _ in range(n+1)]

for _ in range(m):
    node1, node2 = map(int,sys.stdin.readline().rstrip().split())

    graph[node1].append(node2)

q = [(0,x)]

dist = [1E9] * (n+1)
dist[x] = 0

while q:
    cost, node = heapq.heappop(q)

    if dist[node] < cost: continue

    for i in graph[node]:
        newCost, newNode = 1, i

        distance = newCost + cost
        if dist[newNode] > distance:
            dist[newNode] = distance
            heapq.heappush(q,(distance,newNode))
        else:
            continue

if dist.count(k) == 0:
    print(-1)
else:
    for j in range(1,n+1):
        if dist[j] == k:
            print(j)

풀이 설명:

graph에는 도시 ~ 도시 까지 도로 정보를 담습니다. 

for _ in range(m):
    node1, node2 = map(int,sys.stdin.readline().rstrip().split())

    graph[node1].append(node2)

graph에는 도시 ~ 도시 까지 도로 정보를 담습니다. 

 

q = [(0,x)]

dist = [1E9] * (n+1)
dist[x] = 0

그리고 heapq에는 (거리, 도시)의 값이 들어 갑니다. 초기 값은 (0, 시작 도시)로 설정합니다.

dist는 거리를 계산하여 담을 배열로 시작점 ~ 시작점의 거리는 0이므로, 0으로 설정해줍니다.

 

while q:
    cost, node = heapq.heappop(q)

    if dist[node] < cost: continue

    for i in graph[node]:
        newCost, newNode = 1, i

        distance = newCost + cost
        if dist[newNode] > distance:
            dist[newNode] = distance
            heapq.heappush(q,(distance,newNode))
        else:
            continue

while문을 통해서 갈 수 있는 도시들의 정보를 꺼냅니다.

 

다음 heapq를 통해 얻은 정보를 통해 for문으로 graph에서 연결된 도시 정보를 끌어옵니다.

 

마지막으로 연결된 도시의 거리정보를 계산한 다음 계속해서 거리정보 값들 중 작은 값으로 거리 값을 갱신해줍니다.(dist 배열)

 

 

시작점 = 1, 도로 정보 (1,2) (2,3) (3,4) 가 주어졌다고 가정해보겠습니다. 

위 예시를 통해 자세히 설명하자면, heapq에는 초기값 (0,1)가 들어갔다가 while 문 안에서 (0,1)이 pop 되겠죠.

그럼 for문을 통해 1에서 갈 수 있는 2의 값이 꺼내지고(in graph[1]), 도시 1에서 2로 가는 거리의 값인 1이 dist[2]의 값으로 계산 된 후 다시 heapq에는 (1(dist),2(node))가 들어가게 됩니다.

 

그럼 다음 싸이클에서는 newCost = 1, newNode = 2가 나오게 되고, for문을 통해 2에서 갈 수 있는 노드를 찾게되겠죠.

그럼 또 (2,3)인 도로 정보가 graph[2]에 담겨있으니, 이번에는 1->2까지의 거리 + 2->3까지의 거리가 계산된 후 (2(dist),3(node))

결과적으로 노드 4까지 도달하게 되면, 1에서 2,3을 거쳐 4까지 도달하는 최소 거리가 계산되게 됩니다.

 

 

 

 

if dist.count(k) == 0:
    print(-1)
else:
    for j in range(1,n+1):
        if dist[j] == k:
            print(j)

시작점으로 부터 도달할 수 있는 모든 노드의 거리 정보를 계산하고 나면, 다음 구문을 통해 요구하는 결과 값을 출력해줍니다.