lsc4719   9달 전

전 다익스트라 알고리즘을 곧이 곧대로 적용하면 풀리는 문제라고 생각했습니다.
하지만 자꾸 틀리다고 하네요.
제 알고리즘은 다음과 같습니다.
1. 입력을 받아 그래프를 구성한다.
2. 그래프의 1번 노드부터 힙을 이용하여 그리디하게 최단경로를 구한다. (다익스트라 알고리즘)
 * 단, 귀가중에 길이 막히면, 천천히 간다.
3. 1번부터 N번까지 총 N개의 노드 중 가장 늦게 귀가한 집의 귀가시간을 출력한다.
사실 2번 단계의 알고리즘이 항상 최적해를 내주는지 확신하지 못하겠습니다.
하지만, 제가 아는 한도 내에선.. 이렇게 큰 입력이 주어지는 문제는 dp 아니면 다익스트라 알고리즘밖에 해결책이 생각나지 않습니다.
알고리즘에 문제가 있나요?
ps. 그래프의 간선이 갖는 무게는 double 자료형 변수에 저장하였습니다. 혹시 이게 문제가 될까요?

noeffserv   9달 전

다익스트라로 구현한것 자체는 문제가 없을거라 생각합니다. 저도 다익스트라로 구현했거든요.

근데 저도 이 문제 많이 틀렸는데요. 저같은 경우는 출력형식에 문제가 있더군요.

예를 들어, 정답이 5 라면 5로 출력해야 하고 5.5 라면 5.5 라고 출력해야 되는데

5.50000 이렇게 출력해서 틀린답이 되버리더군요. 

혹시 님도 그런 문제가 아닐런지 .. 조심스럽게 추측해봅니다.

lsc4719   9달 전

정말 감사합니다ㅠㅠㅠㅠ 너무 좌절하고 있었는데 ㅋㅋ.. 감사해요!!! 문제의 저지가 스페셜 저지가 아닌데, 실수를 출력해야 하는 문제는, 출력에 신경을 써야겠어요!!

lsc4719   9달 전

위의 질문에 이어서인데요,

이 문제가 다익스트라로 풀릴 수 있는 이유가 무엇일까요?

Q. 모든 edge의 weight이 0이상이면 '항상' 다익스트라 알고리즘으로 최단 경로 문제를 해결할 수 있나요?

 * 이 문제에서처럼 경로에 따라서 edge의 weight이 달라진다고 해도?

noeffserv   9달 전

제가 알기론 음수 사이클만 없다면 다익스트라를 항상 이용가능한걸로 알고있습니다. 


그리고 이 문제에서 에지 중량이 변하는 현상은 있지만 사실 그 변화가 항상 일정하기 때문에 실질적으론 어떤 일정한값의 에지 중량을 다루기 때문에 일반적인 다익스트라문제와 다를바가 없습니다.

lsc4719   9달 전

그 변화가 항상 일정하다는 게 어떤 변화를 말씀하시는 건가요?

퇴근시간이 되면 간선의 가중치가 변하지만, 그 변화가 일정하다는 건가요? 뭔가 일정하다는 것이 무엇인지 잘 모르겠습니다. 혹시 알려주실 수 있나요?

noeffserv   9달 전

뭔가 설명이 부족했네요 ㅠ

문제에 나오는 내용을 도움삼아 뜻을 설명해보겠습니다.


만약 퇴근 시간이 10분부터 20분이고 어떤 도로에 진입한 순간이 15분이며, 도로의 길이는 10이라면 이 도로를 전부 통과하는 데 걸리는 시간은
퇴근 시간 : 5분(15 ~ 20분)동안 간 거리 = 2.5를 가는 데 걸린 시간 : 5분
퇴근 시간 외의 시간 : 나머지 거리 7.5를 가는 데 걸린 시간 : 7.5분
총 12.5분이 된다.


아시다시피 우선 위 같은 경우가 edge 의 weight 가 달라지는 경우인데요.

원래 10분이 걸려야하는 도로이지만 12.5분이 걸립니다.

이 변화는 퇴근시간의 시작시간과 끝 시간에 의해 영향을 받는데요

그런데 이 시작시간과 끝 시간은 처음부터 주어지는 값이죠.

그러므로 에지의 중량이 10에서 12.5로 변화한다해도 12.5에서 다시 17.5나 13.5 기타 등등의 값으로 변하지는 않습니다.

즉, 언제나 12.5가 되는 거죠.

그러므로 다익스트라를 사용하는데 문제가 없다는 뜻입니다.

lsc4719   9달 전

Edge u->v의 중량이 u->v->s 경로로 이동할 때, v->s에서는 이미 지나온 u->v의 중량을 바꿀 수 없고, 이처럼 경로에따라 지나온 경로의 중량이 변할 수 없고 + 모든 간선의 중량이 음이 아닐 때 => 다익스트라를 사용할 수 있다는 건가요?

noeffserv   9달 전

네 그런것 같습니다.

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