jmj45   1년 전

1. 문제 요약
[약속 장소 정하기]
1. 출발 위치는 약속 장소가 아니다.
2. 지헌이의 최단 시간 + 성하의 최단 시간이 최소가 되는 위치
3. 지헌이의 시간 <= 성하의 시간
4. 약속 장소가 여러곳이라면, 지헌이와 가장 가까운 곳이 최종 장소가 됨.
    -> 만약 지헌이와의 거리도 같다면 번호가 가장 작은 순이 최종 장소가 됨.
해당 조건들은 1->2->3->4 순으로 만족해야 하는 것이 관건!!

2. 입출력
[입력]
1. 약속 장소 후보군 V(2<=V<=100), 장소를 연결하는 길이 수 M (1<=M<=1000)
3. 다음 M개의 줄에 a b c 주어짐
   - a : 길의 시작, b : 길의 끝, c : 길을 건너는 시간 (c는 10000이하의 자연수)
   - 길은 양방향이다.
4. 지헌이의 위치 J, 성하의 위치 S

[출력]
- 조건 충족되는 약속 장소의 위치
- 만날 순 있어도 조건이 충족되지 않으면 -1 출력

3. 조건
- 성하와 지헌이가 만날 수 있는 경우만 주어진다.

4. 알고리즘
- 지헌이와 성하의 dijkstra 알고리즘을 각각 수행해 배열을 생성한다.
- 다음과 같은 조건을 가지는 priorityQueue에 지헌과 성하의 다익스트라 배열의 합을 넣는다.
   -> 두 배열의 합이 최소가 되어야 한다.
   -> 합이 같다면, 지헌과 가까워야 한다.
   -> 지헌과 가까운 거리가 같다면, 번호가 작아야 한다.


제가 정리한 내용 및 알고리즘 입니다. 대체 왜 틀린건지..ㅠㅠㅠ 설명해주실 고수분 계신가요..

tmdwp0910   1년 전

2번 조건에 의하면 최소 길이에 해당하는 정점을 우선순위로 구해야 합니다.

하지만 현재 코드는 3번의 조건에 따라 지헌의 거리가 성하보다 더 먼 경우를 먼저 제거하고 있습니다.

따라서, 최소길이를 만족하지만 3번 조건에 의해 -1이 되어야 할 케이스가 최소길이가 아닌 3번 조건이 만족하는 다른 정답이 출력될 수 있습니다.

jmj45   1년 전

감사합니다 덕분에 풀었습니다!!ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.