백준 12834번 주간 미팅

 

문제

문제링크

만약 KIST 기사단 2기로 여러분이 선발된다면, 서울 월곡에 있는 KIST와 양재에 있는 씨알푸드에서 팀이 함께 만나 의논하고 함께 작업할 시간을 가지게 된다. 누구나 그 회의 장소에 빨리 가고 싶은 마음은 똑같을 것이다.

각 장소를 노드로 생각하고, 연결된 도로를 간선으로 생각하면 그래프를 구성할 수 있다. KIST 기사단 N명의 집이 있는 노드 번호와 KIST, 씨알푸드의 노드 번호가 주어지고, 한 사람의 거리 di = (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)로 정의된다. 단, 도달할 수 없는 경우의 최단 거리는 -1로 정의한다. 예를 들어, 어떤 사람이 KIST로는 갈 수 없고 씨알푸드까지의 최단 거리가 10인 경우 이 사람의 거리 d는 9이고, 다른 사람이 KIST, 씨알푸드로 모두 갈 수 없을 경우 이 사람의 거리 d는 -2이다. 이때 Σdi의 값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000)

둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V)

셋째 줄에 팀원 N명의 집의 위치 Hi가 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ Hi ≤ V)

넷째 줄부터 E+3번째 줄까지는 도로의 양 끝 장소 a, b와 길이 l이 주어진다. (1 ≤ a, b ≤ V, 1 ≤ l ≤ 100)

출력

모든 사람의 최단 거리의 합을 출력한다. 단, KIST나 씨알푸드로 갈 수 없는 경우에는 -1로 처리한다.

2. 코드

import sys
from heapq import heappush, heappop

INF = sys.maxsize
inp = lambda: map(int, sys.stdin.readline().split())

# 팀원집 위치를 기반으로 다익스트라 진행
def dijstra(start):
    dis = [INF] * (v + 1)
    dis[start] = 0

    queue = []
    heappush(queue, (0, start))

    while queue:
        dist, now = heappop(queue)

        if dis[now] < dist:
            continue
        for i in maps[now]:
            cost = dist + i[1]

            if cost < dis[i[0]]:
                dis[i[0]] = cost
                heappush(queue, (cost, i[0]))
    return dis

n, v, e = inp()

maps = [[] for _ in range(v + 1)]

# 카이스트 위치, 씨알 푸드 위치
k_p, f_p = inp()

# 팀원들 집 위치
hs = list(inp())

# 거리별 비용 값 집어 넣기
for _ in range(e):
    a, b, c = inp()
    maps[a].append((b, c))
    maps[b].append((a, c))

# 정답
ans = 0

# 팀원들 집 위치 뽑아내기
for i in hs:
    # 거리 합산
    d = 0
    # 팀원집에서 모든 곳을 최소 비용으로 간 배열
    S = dijstra(i)

    # 카이스트 가 갈수있는 곳인지 아닌지 판별
    if S[k_p] == INF:
        d -= 1
    else:
        d += S[k_p]

    # 씨알푸드가 갈수 있는 곳인지 아닌지 판별
    if S[f_p] == INF:
        d -= 1
    else:
        d += S[f_p]
    # 거리 합산
    ans += d
# 출력
print(ans)

3. 회고

Q. 문제를 보고 든 생각 및 해결법

1. 각각 팀원들의 집에서 다익스트라 진행한다.
2. 1번 진행 이후 각각 팀원들 집에서 KIST, 씨알 푸드 최소 비용 배열이 나온다.
3. 이때 최소 비용이 무한 값으로 정의한 INF 값과 동일 한지 판별한다.
4. INF 으로 판별 된곳은 -1, 아닌 곳은 최소 비용으로 거리 값을 합산한다.
5. 1~4 게속 진행하여 나온 합산 된 값을 출력한다. 

4. 고쳐야 할점

4번 진행점 코드가 좀 길다.. 이것을 조금더 줄여보도록 하는 것  생각하면 좋을듯하다..