반응형

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

img

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

  • 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
  • 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
  • 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
  • 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

  • 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

예제 입력 1

2
5 4 2
1 2 3
1 2 6
2 3 2
3 4 4
3 5 3
5
4
6 9 2
2 3 1
1 2 1
1 3 3
2 4 4
2 5 5
3 4 3
3 6 2
4 5 4
4 6 3
5 6 7
5
6

예제 출력 1

4 5
6

나의 풀이

처음에 문제가 잘 이해가 안되서 문제를 이해하는데에만 시간을 좀 많이 사용하였다. 문제를 이해를 하고나서 s에서 g,h를 거쳐가는 최소값과 s에서 바로 target으로 가는 최소값이 같으면 그것이 도착지가 될 수 있다고 생각을 해서 구현을 하였지만 계속 50프로까지 채점이 되다가 틀리게 되었다. 아직도 이 풀이에 대한 잘못된 점을 찾지를 못했지만 아마도 같은 가중치의 다른 경로가 존재할 수 있기때문인 것 같다... 그래서 검색을 해서 다익스트라를 한 번만 사용하여 풀이하는 법을 알게되어 그렇게 풀었다.


g와 h의 거리를 0.1만큼 빼주어서 같은 가중치의 다른 경로는 무시하게끔 만들어 줍니다. 0.1을 빼주어도 다른 최단경로를 구하는데에는 영향을 끼치지 못하는데, 이 이유는 애초에 도착지로 가는 최단경로가 아니라면 가중치가 최소 1이기때문에 0.1은 영향을 끼칠 수가 없기 때문입니다. 따라서 0.1을 빼주어도 아무런 영향을 끼지치않고 앞에서 말한 같은 가중치가 있을 경우를 걸러줄 수 있습니다. 이렇게 0.1을 빼준 순간 g와 h를 거치게 되면 다익스트라를 사용하여 구해진 최단거리를 저장하는 배열에는 float형의 수가 저장이 된다는 것을 이용하면 이 문제를 풀 수 있다. 따라서 그래프의 간선을 입력 받을 때 g와 h를 잇는 간선의 가중치에 -0.1을 해주고 s를 시작점으로 하는 다익스트라를 한 번만 돌리고나서 입력받는 목적지 후보들을 검사하여 INF가 아니고 float형이라면 목적지가 될 수 있다는 의미이다.


코드

  • 다익스트라를 한 번만 사용하는 풀이
# 9370번 미확인 도착지
import sys, heapq
INF = float('inf')

# dijkstra
def dijkstra(n, s, graph):

    # 최단 거리 배열
    d = [INF] * (n+1)
    d[s] = 0

    # 최소 힙
    hq = []
    heapq.heappush(hq, [0,s])

    while hq:
        tmp = heapq.heappop(hq)
        cost = tmp[0]
        node = tmp[1]

        if cost > d[node]:
            continue

        for v in graph[node]:
            neighbor = v[0]
            n_cost = d[node] + v[1]

            if n_cost < d[neighbor]:
                d[neighbor] = n_cost
                heapq.heappush(hq, [n_cost, neighbor])

    return d 

# main
T = int(input())

for _ in range(T):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())

    # 그래프 입력
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, d = map(int, input().split())

        if (a == g and b == h) or (a == h and b == g):
            d -= 0.1    # h와 g 사이의 거리

        graph[a].append([b,d])
        graph[b].append([a,d])

    targets = []
    for _ in range(t):
        targets.append(int(input()))
    targets.sort()

    ans_d = dijkstra(n,s,graph)

    for target in targets:
        if ans_d[target] != INF and type(ans_d[target]) == float:
            print(target, end=' ')
    print()

  • 처음 나의 틀린 풀이
# 9370번 미확인 도착지
import sys, heapq
INF = float('inf')

# dijkstra
def dijkstra(n, s, graph):

    # 최단 거리 배열
    d = [INF] * (n+1)
    d[s] = 0

    # 최소 힙
    hq = []
    heapq.heappush(hq, [0,s])

    while hq:
        tmp = heapq.heappop(hq)
        cost = tmp[0]
        node = tmp[1]

        if cost > d[node]:
            continue

        for v in graph[node]:
            neighbor = v[0]
            n_cost = d[node] + v[1]

            if n_cost < d[neighbor]:
                d[neighbor] = n_cost
                heapq.heappush(hq, [n_cost, neighbor])

    return d 

# main
T = int(input())

for _ in range(T):
    n, m, t = [int(x) for x in sys.stdin.readline().split()]
    s, g, h = [int(x) for x in sys.stdin.readline().split()]

    # 그래프 입력
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, d = [int(x) for x in sys.stdin.readline().split()]
        graph[a].append([b,d])
        graph[b].append([a,d])

        if (a == g and b == h) or (a == h and b == g):
            d_hg = d    # h와 g 사이의 거리

    targets = []
    for _ in range(t):
        targets.append(int(input()))
    targets.sort()

    # s에서 시작하는 최단경로 배열
    d_s = dijkstra(n,s,graph)
    # g에서 시작하는 최단경로 배열
    d_g = dijkstra(n,g,graph)
    # h에서 시작하는 최단경로 배열
    d_h = dijkstra(n,h,graph)

    for target in targets:
        if d_s[target] == d_s[g] + d_hg + d_h[target] or d_s[target] == d_s[h] + d_hg + d_g[target]:
            print(target, end=' ')
    print()
반응형

BELATED ARTICLES

more