rdd6584   1년 전

이 문제를 다이스트라 알고리즘으로 heap에 남아 있는 원소가 없어질때까지 반복하는 것으로 문제를 해결할 수 있었는데요.
플로이드 와샬이 제일 나을거 같기는 한데, 혹시 다이스트라나 비슷한 최단경로 알고리즘 중 이런 최장경로 문제를 더 쉽게 해결할 수 있는 방법이 있을까요?
아니면 최장경로 문제에서 그 외 DP나 DFS말고 다른 효율적인 방법이 있나요?
그리고 추가로 다이스트라는 단순히 BFS+우선순위 큐의 결합으로 정의될 수 있을까요?

고수분들 도와주세요.

chogahui05   1년 전

오. 신기하게 푸셨네요..

그래프 쪽은 해도 해도 팔 게 너무 많습니다.


위상정렬을 하신다면 요거 추천드릴게요.

https://www.acmicpc.net/proble...


그래프 해석도 조금은 익히실 수 있을 거 같습니다아..

rdd6584   1년 전

ehddml3 님

최장경로는 음수간선도 제대로 읽을수 있는 알고리즘에서는 제대로 동작하겠군요. 

DAG같은 경우에는 대부분 위상정렬로도 해결할 수가 있겠네요. 답변 감사합니다.

rdd6584   1년 전

chogahui05  님

사실 지금 위상정렬태그 문제를 위상정렬 아닌 방법으로 깨기 중이었어요ㅋㅋㅋㅋㅋ

그래서 저도 생각못한 방법이 나왔네요.


그리고 저는 여태까지 BFS를 우선순위 큐로 돌리면 다 다익스트라인줄 알았는데, 배열이 1과 0으로만 이루어져 있을때만 가능한 방법이었네요.

최단경로 알고리즘도 하나 제대로 모르고 문제 풀고 있었어요 ㅋㅋㅋㅋ


오늘 라이님 블로그가서 네트워크 플로우나, MCMF같은 알고리즘 처음으로 구경해봤는데요. 진짜 제가 알고있던건 알고리즘도 아니라는 생각이 들더군요..

그래프는 진짜 무궁무진한거 같습니다. 저걸 어떻게 다 이해하고 익힐지 걱정이 되네요.


최종순위 문제도 바로 도전해보겠습니다. 추천 감사합니다.

chogahui05   1년 전

다익으로 푸신 건 신기했습니다.

한 번 코드 보고 연구 함 해보겠습니다. 글고 플로우라던지.. MCMF는 저도 안 했어요..

홍준 시리즈를 풀기 위해서 토너먼트 트리라던지. 다른 것도 해야 하는데.. 못하고 있네요.



rdd6584   1년 전

홍준 시리즈 ㅋㅋㅋㅋ appa님이었나? 그분이 내신 문제집인가요.
배울것들 엄청나게 많네요. 위상정렬도 아직 안했고.. 예전에 자료구조 처음 배울때는 최단경로 알고리즘이 끝판왕인줄 알았더랬죠.
토너먼트 트리는 처음들어보네요.

다익풀이는 그냥 이 문제가 항상 win에서 시작점까지의 최장경로가 정답임을 이용했습니다!

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