mintuchel   1년 전

다익스트라에서 살짝 변형해서 풀었는데 시간초과가 뜨네요.

기존에 memo 배열에서 특정 i번째 노드까지 cnt 수로 간 것보다 크다면 최신화하고 계속 조사하게 했어요.

dp 문제인 것 같은데 다익스트라로 풀면 시간초과때문에 틀리는건지,

아니면 아예 다익스트라로 풀면 안되는건지 궁금하네요!

oh040411   1년 전

다익스트라는 간선의 가중치 합을 최소로 하는 경로를 찾는 알고리즘이고, 이 문제는 가중치 합을 최대로 하는 경로를 찾는 문제입니다. 물론 이 문제를 최단 경로로 풀 수 있긴 하지만, 그러려면 가중치에 -1을 곱해서 음수 간선으로 모델링해야 합니다. 하지만 다익스트라는 가중치가 음이 아닌 정수일 경우에만 빠르게 동작하고, 그렇지 않으면 지수 시간으로 매우 느린 알고리즘입니다. 따라서 이 문제를 다익스트라로 해결하려는 것은 적절한 접근이 아닙니다.

이 문제의 핵심은 간선이 항상 번호가 증가하는 방향을 향하기 때문에, 그래프에 사이클이 존재하지 않는다는 것입니다. 이를 방향 비순환 그래프(directed acyclic graph, DAG)라고 합니다. 이 경우 정점 번호가 증가하는 순서(정확히는 이것이 위상 정렬 순서와 같은데, 이것도 공부해 보시면 좋을 것 같습니다.)대로 dp를 통해 최단/최장 경로를 갱신해주면 쉽게 답을 구할 수 있습니다.

mintuchel   1년 전

덕분에 다익스트라 위상정렬까지 다시 공부하고 해결했습니다!

그래프 문제라 그래프 알고리즘으로 푸는 문제인줄 알았건만 DP 문제였네요ㅎㅎ

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