로그인회원가입
[코딩테스트] 프로그래머스 다익스트라 문제 모음

2026.07.20. 01:23

프로그래머스에서 다익스트라 알고리즘을 연습하기 좋은 대표 문제들은 다음과 같습니다.

입문 (다익스트라 기본)

  1. 배달 (Level 2)

    • 난이도: ★★☆☆☆

    • 핵심: 한 시작점에서 모든 마을까지의 최단 거리

    • 다익스트라의 가장 기본적인 형태를 연습하기 좋습니다.

    • 여러 간선이 존재할 수 있다는 점에 주의하면 됩니다.

기본~중급

  1. 합승 택시 요금 (Level 3)

    • 난이도: ★★★☆☆

    • 핵심:

      • 다익스트라를 여러 번 수행

      • 모든 정점을 합승 지점으로 가정

    • 보통

      • 시작점 S

      • A의 목적지

      • B의 목적지
        에서 각각 다익스트라를 수행합니다.

  1. 가장 먼 노드 (Level 3)

    • 난이도: ★★☆☆☆

    • 사실 BFS로도 풀 수 있지만,

    • 모든 간선의 비용을 1로 생각하면 다익스트라로도 해결 가능합니다.

중급~상급

  1. 등산코스 정하기 (Level 3)

    • 난이도: ★★★★☆

    • 일반적인 다익스트라와 조금 다릅니다.

    • 거리의 합이 아니라 최대 간선 가중치(Intensity) 를 최소화해야 합니다.

    • 우선순위 큐를 사용하는 다익스트라를 변형해서 풉니다.

    • 프로그래머스 다익스트라 문제 중 가장 유명한 편입니다.

  1. 부대복귀 (Level 3)

    • 난이도: ★★★☆☆

    • 목적지에서 역으로 다익스트라(또는 BFS)를 수행하면 효율적으로 해결됩니다.

    • 여러 시작점의 최단거리를 한 번에 구하는 아이디어를 익힐 수 있습니다.

다익스트라 + 응용

  1. 경주로 건설 (Level 3)

    • 난이도: ★★★★★

    • 단순 다익스트라가 아니라

      • 상태(방향)를 함께 관리해야 합니다.

    • (행, 열, 방향)을 하나의 정점으로 생각하는 응용 문제입니다.

  1. 미로 탈출 (Level 4)

    • 난이도: ★★★★★

    • 상태 공간 탐색과 최단 경로가 결합된 문제입니다.

    • 다익스트라 또는 BFS 변형으로 접근할 수 있습니다.

추천 학습 순서

  1. ✅ 배달

  2. ✅ 합승 택시 요금

  3. ✅ 부대복귀

  4. ✅ 등산코스 정하기

  5. ✅ 경주로 건설

이 순서대로 풀면 기본 다익스트라 → 여러 번 실행 → 다익스트라 응용 → 상태를 포함한 최단 경로까지 자연스럽게 익힐 수 있습니다. 특히 코딩테스트에서 자주 나오는 유형을 거의 모두 경험할 수 있습니다.

목록