오늘은 알고리즘 공부 중에서도 핵심 탐색 기법인 **다익스트라(Dijkstra)**와 **백트래킹(Backtracking)**을 심도 있게 정리했다. 이 두 개념은 서로 다른 문제를 풀지만, 공통점이 많다. 우선 둘 다 **“탐색 대상의 공간을 효율적으로 살펴보며, 불필요한 경로를 줄인다”**는 원리를 공유한다.
✨ 오늘의 성취
다익스트라 알고리즘을 처음부터 구현하고, 우선순위 큐로 최적화까지 해냈다.
백트래킹 문제(N-Queen, 빵집 문제)를 풀며 재귀 호출과 **가지치기(Pruning)**의 필요성을 체감했다.
단순히 코드를 이해하는 것을 넘어, 흐름도와 호출 스택을 직접 그려보며 논리 구조를 시각화했다.
📌 처음엔 복잡했지만, 단계를 쪼개고 작은 예제부터 연습하니 문제 해결이 훨씬 쉬워졌다.
💡 다익스트라 알고리즘
정의: 하나의 정점에서 출발해 모든 정점까지의 최단 거리를 구하는 알고리즘. 탐욕적(Greedy) 방식으로, **“가장 가까운 정점을 먼저 확정하고, 그 정점으로부터 다른 노드의 거리를 갱신”**한다.
간선 (Edges): A-B(4), A-C(1), A-D(2), B-D(5), C-D(2), C-E(3), D-F(2), E-F(3)
초기화 단계
시작 정점 A의 거리는 0으로 설정하고, 나머지 정점의 거리는 무한대로 설정합니다.
초기 거리 배열: {A:0,B:∞,C:∞,D:∞,E:∞,F:∞}
방문하지 않은 정점 집합: {A,B,C,D,E,F}
현재 방문하지 않은 정점 중 가장 거리가 짧은정점 A를 선택합니다.
정점 A에서 갈 수 있는 모든 인접한 정점의 거리를 업데이트합니다:
A-B: 0 + 4 = 4
A-C: 0 + 1 = 1
A-D: 0 + 2 = 2
업데이트 후 거리 배열: {A:0,B:4,C:1,D:2,E:∞,F:∞}
정점 A를 방문한 것으로 표시하고 방문하지 않은 정점 집합에서 제거: {B,C,D,E,F}
현재 방문하지 않은 정점 중 가장 거리가 짧은정점 C를 선택합니다.
정점 C에서 갈 수 있는 모든 인접한 정점의 거리를 업데이트합니다:
C-D: 1 + 2 = 3 (기존의 D까지의 거리 2보다 크므로 업데이트하지 않음)
C-E: 1 + 3 = 4
업데이트 후 거리 배열: {A:0,B:4,C:1,D:2,E:4,F:∞}
정점 C를 방문한 것으로 표시하고 방문하지 않은 정점 집합에서 제거: {B,D,E,F}
재 방문하지 않은 정점 중 가장 거리가 짧은정점 D를 선택합니다.
정점 D에서 갈 수 있는 모든 인접한 정점의 거리를 업데이트합니다:
D-F: 2 + 2 = 4
업데이트 후 거리 배열: {A:0,B:4,C:1,D:2,E:4,F:4}
정점 D를 방문한 것으로 표시하고 방문하지 않은 정점 집합에서 제거: {B,E,F}
현재 방문하지 않은 정점 중 가장 거리가 짧은정점 B를 선택합니다.
정점 B에서 갈 수 있는 모든 인접한 정점의 거리를 업데이트합니다:
B-D: 4 + 5 = 9 (기존의 D까지의 거리 2보다 크므로 업데이트하지 않음)
업데이트 후 거리 배열: {A:0,B:4,C:1,D:2,E:4,F:4}
정점 B를 방문한 것으로 표시하고 방문하지 않은 정점 집합에서 제거: {E,F}
마지막으로 방문하지 않은 정점 F를 선택합니다.
정점 F에서 갈 수 있는 모든 인접한 정점의 거리를 업데이트합니다 (이미 모든 거리가 최단 거리로 업데이트됨).
정점 F를 방문한 것으로 표시하고 방문하지 않은 정점 집합에서 제거: {}
최종 결과: 정점 A로부터 각 정점까지의 최단 거리는 다음과 같습니다:
A: 0 B: 4 C: 1 D: 2 E: 4 F: 4
💡 백트래킹
정의: 가능한 해의 공간을 깊이 우선 탐색(DFS)하며, 조건을 위배하면 즉시 탐색을 중단하고 되돌아가는 방식.
모든 해를 탐색하지만, 불필요한 경로를 일찍 끊어서 효율을 높이는 알고리즘
특징: “선택 → 조건 확인 → 위배 시 Backtrack → 조건 만족 시 다음 단계”
완전 탐색을 기반으로, “조건을 위배하는 경로는 더 이상 탐색하지 않는다”는 가지치기(pruning)를 적용하는 기법
아이디어
현재 상태에서 선택 가능한 모든 경우를 시도.
조건을 만족하지 않으면 더 깊이 탐색하지 않고 되돌아감 (Backtrack).
조건을 만족하는 해를 찾으면 저장하거나 출력.
예시 : 순열, 조합, N-Queen, 미로 탐색, 부분집합 문제 등에서 쓰임
장점: 완전 탐색보다 훨씬 효율적, 해가 여러 개인 문제를 전부 탐색 가능.
단점: 최악의 경우 여전히 경우의 수가 많아질 수 있음.
📌 백트래킹과 비슷한 기법과 차이
DFS: 모든 경로 탐색 (가지치기 없음)
DP: 부분 문제의 결과를 저장해서 효율적으로 해결
Greedy: 매 단계 최적 선택
Backtracking: 모든 경우의 수 탐색 + 불가능한 경우 빠르게 포기
🌳 백트래킹의 기본 흐름
문제 정의 & 상태 표현
탐색해야 하는 문제를 “트리(혹은 그래프)의 상태 공간”으로 표현
각 노드는 현재까지의 선택(부분 해)을 의미
종료 조건(Base Case) 확인
현재 상태가 문제의 해(목표) 조건을 만족하면 → 결과를 기록
더 이상 진행할 필요가 없으면(범위 벗어남, 조건 위배) → 탐색 중단
후보군 탐색 (DFS)
현재 상태에서 선택할 수 있는 모든 “후보(move)”를 순회
각 후보를 선택 → 상태를 갱신 → 재귀 호출(깊이 탐색)
Pruning (가지치기)
중간에 “이 선택은 해답이 될 수 없음”이 확실하면, 더 깊이 탐색하지 않고 돌아감
예: N-Queen에서 이미 같은 열/대각선에 퀸이 있으면 바로 종료
복원 (Backtrack)
재귀가 끝난 후, 이전 상태로 돌아가 다음 후보를 탐색
이렇게 해서 모든 가능성을 확인
🧩 간단 예시 (부분 순열)
static int N = 3, M = 2;
static int[] result = new int[M];
static boolean[] used = new boolean[N + 1];
static void backtrack(int depth) {
if (depth == M) {
System.out.println(Arrays.toString(result));
return;
}
for (int i = 1; i <= N; i++) {
if (!used[i]) {
used[i] = true;
result[depth] = i;
backtrack(depth + 1);
used[i] = false; // Backtrack
}
}
}
⚡ 알고리즘 비교
알고리즘
탐색 방식
장점
단점
다익스트라
탐욕적(Greedy) + 우선순위 큐
가중치 있는 그래프의 최단 경로
음수 가중치 불가
BFS
레벨 탐색
단순 구현, 무가중치 최단 거리
가중치가 있으면 부적합
백트래킹
DFS 기반
불필요한 탐색을 줄임
최악의 경우 여전히 지수적 탐색
📈 시간 복잡도 분석
다익스트라: O(E log V) (우선순위 큐 사용)
백트래킹(N-Queen): 최악은 O(N!), 하지만 Pruning으로 평균 탐색 시간은 크게 줄어든다.
