백준 14221번 <편의점>

백준 알고리즘 14221번

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

14221번: 편의점

---

14221번

입력으로 첫 줄에는 정점의 개수 n, 간의 개수 m이 어진다. 그 다음 m줄에 걸쳐 간선의 정보가 주어진다.

이때 a, b, c가 주어지는데 이는 a, b를 잇는 간선의 거리가 c라는 의미이다.

 

다음 줄에는 집의 후보지의 개수 p와 편의점의 개수 q가 주어진다. 그 다음줄에는 집의 후보지들의 정점번호, 그 다음 줄에는 편의점의 정점번호가 주어진다.

 

츨력으로는 편의점으로부터 가장 가까운 거리에 있는 집 후보의 정점번호를 출력하면 된다. 이때 거리가 같은 곳이 여러 곳이라면 정점 번호가 제일 작은 것을 출력하면 된다.

---

문제 해결

다익스트라 알고리즘을 활용하여 해결하였다.

다익스트라 알고리즘은 한 정점에서 나머지 정점까지의 최소 거리를 모두 구하는 알고리즘이다.

 

다익스트라 알고리즘을 이용하여 각 집 후보지에서 편의점까지의 최소 거리를 구한 뒤, 그 중에서 가장 거리가 가까운 집 후보지를 선택하고 만약 같은 거리라면 그 중 정점번호가 낮은 것을 선택하면 된다.

---

코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]

    for _ in range(m):
        start, end, cost = map(int, input().split())
        graph[start].append((end, cost))
        graph[end].append((start, cost))

    homeNum, convNum = map(int, input().split())

    home = list(map(int, input().split()))
    convenience = list(map(int, input().split()))

    short = []
    for i in home:
        short.append(dijkstra(graph, i, n))

    result = []
    min = INF
    for i in range(homeNum):
        for j in convenience:
            if min > short[i][j]:
                min = short[i][j]

    for i in range(homeNum):
        for j in convenience:
            if min == short[i][j]:
                result.append(home[i])

    result.sort()
    print(result[0])

def dijkstra(graph, start, n):
    distance = [INF] * (n+1)

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

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]

            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance

main()

---

결과

---

무방향 그래프인데 방향 그래프로 생각해서 graph에 a->b만 넣고 b->a는 안넣어서 처음에 틀렸다.