AndroidTeacher

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

문제 설명

도시들의 번호와 각 도시 사이의 거리가 주어지며 목표 거리가 주어질 때, 출발 도시에서 도착도시 까지의 최단거리가 목표거리인 도시들을 출력하는 문제이다.

예를 들어, 출발 도시가 1이고 목표 거리가 5일 때, 도시 2,3,4 까지의 최단거리가 5이면 2,3,4를 출력하면 된다.

아무 도시도 없으면 -1을 출력한다. 

풀이 과정

이 문제는 다익스트라(Dijkstra)로 풀 수도 있고 BFS를 이용해서 풀어도 된다.

BFS풀이는 다른 블로그에도 많이 올라와 있는 것 같아 다익스트라로 풀어보았다.

① 리스트 distance를 통해 초기 거리를 모두 무한으로 초기화 한다. 

② a, b를 통해 그래프의 출발점 A로 부터 연결된 도착점 B들을 연결해준다.

    연결된 거리는 항상 1이라고 했으므로 거리를 따로 저장할 필요는 없다.

③ heapq를 이용해 거리가 짧을수록 앞에 오는 큐(우선순위 큐)를 만든다.

④ 처음 자기자신과의 거리는 0으로 설정하고 현재 나의 지점과 연결된 점들과의 거리를 누적거리+1 한다.

    반복하여 출발지점으로부터 도달할 수 있는 모든 도시들에 대해 수행한다.

    ( 이 때, 가야 하는 곳의 거리가 이미 저장되어 있는 거리보다 크다면 이미 더 짧은 방법으로 방문했다는 뜻이므로 skip)

⑤ distance가 x인 지점들을 출력하면 된다.

import heapq
import sys

INF = int(1e9)
n, m, k, x = map(int, sys.stdin.readline().split())

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

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue
        for i in graph[now]:
            cost = dist + 1
            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(q, (cost, i))

dijkstra(x)
flag = 0
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        flag = 1

if flag == 0:
    print(-1)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !