BOJ 미확인 도착지2 [BOJ]9370번: 미확인 도착지 문제: https://www.acmicpc.net/problem/9370 아이디어가 필요한 최단경로 문제입니다. 시작점 S, 도착점 T 그리고 중간지점 노드를 G, H라 하겠습니다. 후보 T 노드를 가는 S->T 경로중에 G-H를 경유해서 가는 T노드가 몇 개 있는지 구하는 문제입니다. 일일이 지나온 경로를 저장해서 찾아도 되지만 그렇게 하면 시간초과가납니다. 해결방법은 S->T 경로를 다음과 같이 정의하는 것입니다. S->G->H->T 또는 S->H->G->T 다익스트라(start, end)의 리턴값을 출발 노드(start)부터 도착 노드(end)까지의 거리로 가정하겠습니다. 이 때 아래 조건을 만족하는 T를 전부 구하면 됩니다. 다익스트라(start: S, end: T) = 다익스트라(start: S.. 2022. 3. 24. [BOJ]9370번: 미확인 도착지 www.acmicpc.net/problem/9370 문제를 잘 읽어보셔야 합니다. 출발지 -> 후보지로 가는 최단 경로 중에 주어진 경로 g,h가 포함된 후보지를 고르는 문제입니다. 저는 문제 잘못 읽어서 가장 짧은 후보지 고르는 줄 알고 헤맸습니다. 출발지 s, 후보지 c, 주어진 경로 g,h라고 한다면 1. 출발지에서 다익스트라를 돌립니다. 2. 주어진 경로 g, h에서 다익스트라를 돌립니다. 그리고 두 조건 중 하나를 만족하면 정답입니다. 1. 출발지 → 후보지 거리 == 출발지 → g 거리 + g 거리 → h 거리 + h 거리 →후보지 거리 2. 출발지 → 후보지 거리 == 출발지 → h 거리 + h 거리 → g 거리 + g 거리 →후보지 거리 정답 후보는 최단 경로에 g,h 경로가 포함되어 있음.. 2021. 2. 8. 이전 1 다음
