[백준] 9370번(python 파이썬) - 미확인 도착지

문제 링크: https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	256 MB	19755	5534	3532	24.577%

문제

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

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

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

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 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. 입력받은 도로의 간선들을 road[a] = (b, 거리) 느낌으로 저장해준다. (a 는 출발 b는 도착)

2. 물론 양방향도로이므로  road[b] = (a, 거리) 도 저장

3. 우리는 범죄자들이 h-g 도로를 지난 것을 알고 있다. -> 목적지 도달할떄 반드시 지남

 -> flag로 표시를 해보자 ( 지났으면 -1 아님 0 )

4. 모든 도로를 전부 탐색해봐야하기 때문에 다익스트라 알고리즘을 쓴다. (시간 3초-> 넉넉)

5. 여기서 범죄자들은 h-g도로를 지나면서 출발지에서 목적지로가는 최단경로로 움직이기 때문에
    dist가 지금까지 온 거리라고 한다면 그리고 dist < (이전에 도착했을때 나온 거리)가 성립한다면

    dist를 distance[현재 위치] = dist 식을 적용해야한다. (distance는 최단거리 기록하는 list)

6. 근데 여기서 생각해야 할 것 h-g지점을 거쳐온 거리와 거쳐오지 않은 거리를 비교해야할 때가 있다.

    이 부분에서 나는 힙 정렬을 사용했다. (두개의 거리가 같을 때 flag = -1이므로 먼저 위치하게 되므로

    heappop을 사용할때 먼저 추출)

7. heapq.heappop으로 먼저 추출된 거리를 distance에 넣음 

8. dist >= (이전에 도착했을때 나온 거리) 일 경우 넘김

9. 8의 과정을 지났다면 다음 지점까지의 거리 비교 ,for문사용 ( 시간복잡도 줄임 )

10.현재위치가 h 다음 지점 위치 g라면(or 반대도 가능) heapq에 flag를 -1로 해서 넣음

11. 과정반복

12. 결과 출력

 

 어휴 복잡하다 복잡해 .....

 

이 문제풀고 좀 늙은 것 같다... 

재미있는 점은 문제푸는 것 보다 변수이름을 어떻게 정할 지 고민한게 더 힘들었다는 점 ㅋㅋ

 

다른사람 풀이를 보고 위안을 받았다ㅎㅎ

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

나도 어쨌든 풀었으니 .... 오케이 인정....

 

이만 풀이를 마치겠다ㅋㅋ

 

 

 

구현 코드

---

from sys import stdin
import heapq
input = stdin.readline
INF = float('inf')

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, 0, start)) # 거리 flag 위치 순서임

    while q:
        dist, flag, curr = heapq.heappop(q)

        if distance[curr] <= dist:
            continue

        distance[curr] = dist
        flaghg[curr] = flag

        for next, next_dist in roads[curr]:
            cost = dist + next_dist
            if distance[next] >= cost:
                if (next, curr) == (h, g) or (next, curr) == (g, h):
                    heapq.heappush(q, (cost, -1, next))
                else:
                    heapq.heappush(q, (cost, flag, next))



T = int(input())
ans = []

for _ in range(T):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())
    roads = [[] for _ in range(n + 1)]
    distance = [INF] * (n + 1) # 무한대로 거리 설정
    flaghg = [0] * (n + 1) # h-g 구간을 지났는지 저장해놓는 list
    destinations = set() #목적지를 저장해 놓는 집합

    for _ in range(m):
       a, b, d = map(int, input().split())
       roads[a].append((b, d))
       roads[b].append((a, d))

    for _ in range(t):
       destinations.add(int(input()))

    dijkstra(s)


    trueflaghg = set([x for x in range(n + 1) if flaghg[x] == -1])
    resList = sorted(list(destinations.intersection(trueflaghg))) # 교집합 -> 정답임
    ans.append(resList)

for answer in ans:
    for res in answer:
        print(res, end=' ')
    print()