• 개인 공부 목적으로 작성한 포스팅입니다.
  • 아래 출처를 참고하여 작성하였습니다. :)

다익스트라 문제 접근 시 활용할 수 있는 팁에 대해 알아보겠습니다.

역방향 간선 고려하기

  • 문제에서 간선이 단방향으로 주어질 때 역방향 간선을 활용해서 문제를 해결해야 할 수도 있습니다.

예시문제: BOJ17835번: 면접보는 승범이네

  • 위 문제의 경우 역방향 간선을 구해서 면접장 -> 도시의 거리를 구하는 방식으로 해결해야 합니다.

시작 노드 여러 개 넣기

  • 다익스트라의 일반 예시는 시작 정점을 한 개만 놓고 풉니다.
  • 하지만 시작 정점을 여러개로 두고 다익스트라를 한 번만 돌릴 수도 있습니다.
  • 처음 dist배열 초기화 시 dist[i] = 0, dist[j] = 0 이렇게 여러 개를 0으로 초기화하면 됩니다.

예시문제: BOJ17835번: 면접보는 승범이네

  • 위 문제의 경우 모든 면접장을 시작 정점으로 놓고 다익스트라를 한 번만 돌려도 문제의 조건에 위반되지 않습니다.
  • 일반적으로 N개 정점에서 각각 최단 경로를 구하기 위해서는 다익스트라를 N번 돌려야 하지만, 이렇게 문제 조건을 통해서 특수하게 만족시킬 수 있다는 걸 기억합시다.

시간 복잡도 힌트

  • 다익스트라를 무작정 많이 돌릴 수 없는 문제는 반드시 시간복잡도를 줄일 수 있는 방법이 있습니다.
  • 그 중 하나가 다익스트라를 사용하면 최단 경로의 간선 갯수는 최대 N-1개라는 점입니다.
    • 다익스트라는 ‘양의 간선’을 가정하므로 생기는 특징입니다.

예시문제: BOJ2325번: 개코전쟁

  • 위 문제의 경우 “개미왕국은 최단거리로 이동한다.”라는 조건이 있습니다.
  • 위 조건으로 제거대상으로 조사할 간선은 M개(50만)에서 N-1개(1000개)로 줄어듭니다.
  • 이 문제는 N 범위가 1000이므로 1000번 다익스트라를 돌려도 시간초과가 나지 않습니다.