아마 하나하나 다익스트라 하면 시간복잡도 때문에 안될 거예요
구체적인 반례:
1000 1000
1 1 1 ..... 1
1 1 1 ..... 1
. . . .
. . . .
. . . .
1 1 1 ..... 1
7576번 - 토마토
아마 하나하나 다익스트라 하면 시간복잡도 때문에 안될 거예요
구체적인 반례:
1000 1000
1 1 1 ..... 1
1 1 1 ..... 1
. . . .
. . . .
. . . .
1 1 1 ..... 1
댓글을 작성하려면 로그인해야 합니다.
kjk9704 1년 전 2
이 문제에 # 최단 경로 태그가 붙어 있어서 좀 당황할 수 있습니다.
이 문제 다익스트라 알고리즘 써야 하나? 아니면 플로이드 워셜 알고리즘을 써야 하나?
그러나 이 문제는 사실 문자 그대로 최단 경로의 길이만 구하면 되는 문제라
14940번 문제(쉬운 최단거리)처럼 bfs 알고리즘만 잘 구현하면 되는 문제입니다.
그런데 이쯤이면 궁금한 것이 생기는데 그러면 최단 경로의 의미는 무엇일까요?
최단 경로는 말 그대로 가장 짧은 경로의 길이를 구하는 알고리즘으로
최단 경로 알고리즘의 기초는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘으로 이루어져 있습니다.
왜 이 두 알고리즘이 기초인지는 아래의 코드를 확인해주세요.
N = 3이라고 할 때
0번 지점 -> 1번 지점
1번 지점 -> 2번 지점
2번 지점 -> 3번 지점
이렇게 0->1->2->3 단방향으로만 간다고 가정합니다.
그런데 하나의 지점으로부터 다른 지점으로 가는 단방향 경로가 하나가 아닌 2개 이상 존재할 수 있습니다.
예시로 0번 지점에서 1번 지점으로 가는 단방향 경로가 3개 존재하며 그 경로들의 가중치는 1,2,3입니다.
이 때 최단 경로로 가야 하므로 최적해는 (무조건 가장 짧은 경로를 선택한다)이므로 0번 지점 -> 1번 지점으로 가는데 최단 경로 길이는 1입니다.
여기서 그리디 알고리즘이 사용된 것을 확인할 수 있습니다.
그런데 일일히 최단 경로 길이를 구하고 마지막에 한꺼번에 더할려고 하면 시간 효율성이 저하됩니다.
최단 경로 길이를 저장해서 활용할 수는 없을까요?
초기값을 0으로 하고 각 최단 경로 길이들을 미리 더해주고 마지막 결과값만 출력하면 해결됩니다.
예시로 N = 3이고 각 단방향 경로의 가중치는 다음과 같습니다.
0번 지점 -> 1번 지점 : 1, 2, 3
1번 지점 -> 2번 지점 : 4, 5
2번 지점 -> 3번 지점 : 6, 7, 8, 9
초기값 dp[0] = 0으로 설정하고 dp[1]을 구해봅니다.
0번 지점 -> 1번 지점 최단 경로 길이는 1이고 이전 결과값 dp[0] = 0이므로 이 값들을 바탕으로 dp[1]을 구합니다.
dp[1] = 0 + 1 = 1
그 다음 1번 지점 최단 경로 길이는 4이고 이전 결과값 dp[1] = 1이므로 이 값들을 바탕으로 dp[2]를 구합니다.
dp[2] = 1 + 4 = 5
같은 원리로 dp[3]을 구합니다.
dp[3] = 5 + 6 = 11
이렇게 해서 0번 지점 -> 3번 지점으로 가는 최단 경로 길이는 11로 구해지고 이것은 dp[3]과 일치합니다.
이렇게 해서 다이나믹 프로그래밍 알고리즘을 활용해서 더 빠르고 효율적으로 최단 경로 길이를 구할 수 있게 됩니다.
이처럼 최단 경로 알고리즘은 그리디 알고리즘 + 다이나믹 프로그래밍 알고리즘가 기초가 된 것을 확인할 수 있습니다.
이 개념은 나중에 class 4에서 나올 데이크스트라(다익스트라) 알고리즘 기초가 됩니다.
제가 class 3 에센셜 문제들을 복습하는 과정에서 얻게 된 정보를 공유합니다.