[LG U+ 유레카 4기] WEEK 04 - 알고리즘 (10)

Soohwan Lim·2026년 4월 28일
algorithm멀티캠퍼스부트캠프부트캠프유레카4기

유레카부트캠프

목록 보기
18/31
post-thumbnail

다익스트라 (Dijkstra), 이진 트리, 서로소, MST크루스칼

1. 오늘의 학습 흐름

  • 다익스트라 알고리즘 개념
  • 인접 리스트 + 순차 탐색 버전 O(V²)
  • 인접 리스트 + PriorityQueue 버전 O(ElogV)
  • BOJ 3109 빵집 (BackTracking 복습)
  • BOJ 1753 최단경로 (다익스트라 적용)
  • 완전 이진 트리 (배열 표현, 전위/중위/후위 순회)
  • 서로소 집합 (Disjoint Set)
  • MST 크루스칼 알고리즘

2. 다익스트라란

단일 출발점에서 양의 가중치를 갖는 그래프의 모든 정점까지 최단 거리를 구하는 알고리즘이다.

음의 가중치가 있으면 다익스트라를 쓸 수 없다. 그 경우엔 벨만-포드 알고리즘을 써야 한다.

핵심 아이디어: 현재까지 최단 거리가 확정된 정점을 경유지로 사용해서, 각 정점까지의 기존 거리와 경유지를 거쳐 가는 거리를 비교해 더 짧은 거리로 갱신한다.

기존에 알고 있는 최단 거리  vs  새 경유지를 통해 가는 거리
→ 더 짧으면 갱신

필요한 자료구조:

  • dist[]: 출발점에서 각 정점까지의 최단 거리 (INF로 초기화)
  • visited[]: 최단 거리가 확정된 정점 표시

시간복잡도:

  • 순차 탐색 버전: O(V²)
  • PriorityQueue 버전: O(E logV)

3. 다익스트라 동작 과정

Step 0. 초기화
  - dist[] = 전부 INF
  - visited[] = 전부 false
  - dist[start] = 0

Step 1. dist[start] = 0 설정

Step 2. V-1번 반복
  Step 2-1. 방문하지 않은 정점 중 dist가 최소인 정점 선택 (minIdx)
  Step 2-2. visited[minIdx] = true
  Step 2-3. minIdx와 인접한 정점들에 대해
            if dist[next] > dist[minIdx] + 가중치 → 갱신

한 번 방문 처리된 정점의 거리는 더 이상 갱신될 수 없다. 이미 최단 거리가 확정됐기 때문이다.

4. 버전 1 - 순차 탐색 O(V²)

static void dijkstra(int st) {
    boolean[] visit = new boolean[V];
    Arrays.fill(dist, INF);
    dist[st] = 0;

    for (int i = 0; i < V - 1; i++) {
        // Step 2-1: 미방문 정점 중 dist 최솟값 찾기
        int minIdx = -1, min = Integer.MAX_VALUE;
        for (int j = 0; j < V; j++) {
            if (!visit[j] && min > dist[j]) {
                min = dist[j];
                minIdx = j;
            }
        }
        if (minIdx == -1) break;  // 연결되지 않은 컴포넌트면 종료

        visit[minIdx] = true;

        // Step 2-3: 인접 정점 거리 갱신
        for (Node cur : list[minIdx]) {
            if (dist[cur.v] > dist[minIdx] + cur.w) {
                dist[cur.v] = dist[minIdx] + cur.w;
            }
        }
    }
}

매번 V개의 정점을 전부 순회해서 최솟값을 찾기 때문에 O(V)가 V번 반복돼 O(V²)다.

5. 버전 2 - PriorityQueue O(ElogV)

버전 1의 병목은 "미방문 정점 중 최솟값 찾기"에서 O(V) 순회가 발생한다는 것이다. PriorityQueue를 쓰면 이 과정이 O(logV)로 줄어든다.

static void dijkstra(int st) {
    PriorityQueue<Node> pq = new PriorityQueue<>();  // Node는 거리 기준 오름차순
    Arrays.fill(dist, INF);
    dist[st] = 0;
    pq.offer(new Node(st, 0));

    while (!pq.isEmpty()) {
        Node now = pq.poll();  // 현재 dist 최소인 정점 꺼내기

        // 이미 더 짧은 거리로 갱신된 경우 skip (visited 배열 대신)
        if (dist[now.v] < now.w) continue;

        for (Node next : list[now.v]) {
            int newCost = dist[now.v] + next.w;
            if (dist[next.v] > newCost) {
                dist[next.v] = newCost;
                pq.offer(new Node(next.v, newCost));  // 갱신된 거리로 pq에 넣기
            }
        }
    }
}

visited 배열 대신 if (dist[now.v] < now.w) continue 조건으로 중복 처리를 막는다. 이미 더 짧은 경로로 갱신됐다면 꺼낸 노드를 무시한다.

PQ에 같은 정점이 여러 번 들어갈 수 있다. 갱신될 때마다 넣기 때문이다. 그래서 꺼낼 때 최신 dist와 비교해서 낡은 값이면 skip하는 것이다.

6. 두 버전 비교

순차 탐색 버전PQ 버전
최솟값 탐색O(V) 순회O(logV) PQ poll
시간복잡도O(V²)O(E logV)
적합한 경우정점 수 V가 적을 때간선 수 E가 많을 때
구현 복잡도단순약간 복잡

정점 수 V가 작고 간선이 많은 밀집 그래프(Dense Graph)라면 O(V²)이 더 유리할 수도 있다. 보통 코테에서는 PQ 버전을 쓴다.

7. 인접 리스트 구성

static class Node implements Comparable<Node> {
    int v, w;  // 도착 정점, 가중치
    public Node(int v, int w) { this.v = v; this.w = w; }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.w, o.w);  // 가중치 오름차순
    }
}

// 초기화
List<Node>[] list = new ArrayList[V];
for (int i = 0; i < V; i++) list[i] = new ArrayList<>();

// 간선 추가 (u → v, 가중치 w)
list[u].add(new Node(v, w));

Node가 Comparable을 구현해야 PriorityQueue에서 자동 정렬된다. 가중치 기준 오름차순으로 Integer.compare(this.w, o.w)를 쓴다.

8. BOJ 3109 빵집 (BackTracking 복습)

어제 배운 BackTracking을 복습 겸 적용한 문제다. 맨 왼쪽 열에서 맨 오른쪽 열까지 우상/우/우하 방향으로만 이동하는 파이프 경로를 최대한 많이 뚫는 문제다.

// 방향: 우상, 우, 우하
static int[][] dir = {{-1,1}, {0,1}, {1,1}};

public static boolean back(int r, int c) {
    if (c == C - 1) { answer++; return true; }

    map[r][c] = 'x';  // 방문 처리 (벽으로 막기)

    for (int i = 0; i < 3; i++) {
        int nr = r + dir[i][0], nc = c + dir[i][1];
        if (nr > -1 && nr < R && nc < C && map[nr][nc] != 'x') {
            if (back(nr, nc)) return true;  // 성공하면 바로 리턴
        }
    }
    // visited[r][c] = false 하면 시간 초과!
    return false;
}

visited 복원을 하지 않는 게 핵심이다. 실패한 경로는 다른 출발점에서도 실패하기 때문에 x로 막아두면 중복 탐색을 줄일 수 있다. visited를 복원하면 같은 실패 경로를 반복해서 탐색하게 되어 시간 초과가 난다.

상단 행부터 탐색하는 이유: 위쪽 행이 먼저 경로를 뚫어야 아래 행도 기회가 생긴다. 아래부터 탐색하면 위 행이 사용할 수 있는 경로를 먼저 막아버린다.

9. BOJ 1753 - 최단경로

오늘 배운 다익스트라를 바로 적용하는 문제다. 정점 번호가 1부터 시작하는 것에 주의한다.

// 1-indexed 처리
list = new ArrayList[V + 1];
dist = new int[V + 1];
for (int i = 1; i <= V; i++) {
    list[i] = new ArrayList<>();
    dist[i] = INF;
}

출력이 많을 때 StringBuilder로 모아서 한 번에 출력하는 패턴도 중요하다.

StringBuilder sb = new StringBuilder();
for (int i = 1; i <= V; i++) {
    if (dist[i] == INF) sb.append("INF\n");
    else sb.append(dist[i]).append("\n");
}
System.out.print(sb);

10. 완전 이진 트리 (Complete Binary Tree)

트리를 배열로 표현하는 방법이다. 인덱스 0은 사용하지 않고 1부터 시작한다.

          A(1)
        /       \
      B(2)      C(3)
     /   \     /   \
   D(4) E(5) F(6) G(7)

인덱스 규칙:

  • 왼쪽 자식: i << 1 (= i*2)
  • 오른쪽 자식: (i << 1) + 1 (= i*2+1)
  • 부모: i >> 1 (= i/2)

배열 하나로 트리 구조를 표현할 수 있어서 메모리 효율적이다.

11. 트리 순회 (DFS)

// 전위 순회 (Pre-order): 루트 → 왼 → 오
void dfsByPreOrder(int cur) {
    if (cur <= lastIndex) {
        System.out.print(nodes[cur] + " ");  // 먼저 방문
        dfsByPreOrder(cur << 1);
        dfsByPreOrder((cur << 1) + 1);
    }
}
// 결과: A B D E C F G

// 중위 순회 (In-order): 왼 → 루트 → 오
void dfsByInOrder(int cur) {
    if (cur <= lastIndex) {
        dfsByInOrder(cur << 1);
        System.out.print(nodes[cur] + " ");  // 중간에 방문
        dfsByInOrder((cur << 1) + 1);
    }
}
// 결과: D B E A F C G

// 후위 순회 (Post-order): 왼 → 오 → 루트
void dfsByPostOrder(int cur) {
    if (cur > lastIndex) return;
    dfsByPostOrder((cur << 1) + 1);
    dfsByPostOrder(cur << 1);
    System.out.print(nodes[cur] + " ");  // 마지막에 방문
}
// 결과: D E B F G C A

DAY09에서 재귀 호출 전/후 출력 차이를 배웠는데 여기서 그대로 나왔다. 전위는 재귀 전, 중위는 재귀 사이, 후위는 재귀 후에 출력한다.

12. 서로소 집합 (Disjoint Set)

서로 중복 원소가 없는 집합들을 표현하는 자료구조다. 각 집합의 대표자(root)를 통해 집합을 구분한다.

세 가지 연산:

static int[] p;  // p[i] = i의 부모

// 1. makeSet: 각 원소를 자기 자신을 root로 초기화
static void make() {
    for (int i = 0; i < N; i++) p[i] = i;
}

// 2. findSet: x의 root(대표자) 찾기
static int find(int v) {
    if (p[v] == v) return v;       // 자신이 root면 반환
    return p[v] = find(p[v]);      // 경로 압축 최적화
}

// 3. union: 두 집합 합치기
static boolean union(int a, int b) {
    int aRoot = find(a), bRoot = find(b);
    if (aRoot == bRoot) return false;  // 같은 집합 → 사이클 발생
    p[bRoot] = aRoot;  // b의 root를 a의 root 아래로
    return true;
}

find()에서 p[v] = find(p[v])로 경로를 압축하면 이후 탐색이 O(1)에 가깝게 빨라진다.

같은 집합인지 확인: find(a) == find(b)
사이클 감지: union이 false를 반환하면 두 정점이 이미 같은 집합 → 사이클 존재

13. MST - 크루스칼 알고리즘

MST(Minimum Spanning Tree, 최소 신장 트리)는 N개의 정점을 N-1개의 간선으로 모두 연결하되 가중치 합이 최소인 트리다.

신장 트리를 완전 탐색으로 구하면 eCn-1이라 n=100이면 5000C99로 불가능하다. 크루스칼은 Greedy를 적용해서 O(ElogE)로 해결한다.

크루스칼 동작 방식:
1. 간선을 가중치 오름차순으로 정렬
2. 가중치가 작은 간선부터 선택
3. 선택 시 사이클이 생기면 skip (Disjoint Set으로 판단)
4. V-1개의 간선이 선택되면 종료

// 간선 클래스
static class Edge implements Comparable<Edge> {
    int from, to, w;
    public int compareTo(Edge o) { return Integer.compare(this.w, o.w); }
}

// 크루스칼
Arrays.sort(edgeList);  // 간선 오름차순 정렬

int result = 0, count = 0;
for (Edge edge : edgeList) {
    if (union(edge.from, edge.to)) {  // 사이클 없으면 선택
        result += edge.w;
        if (++count == V - 1) break;  // V-1개 선택되면 완성
    }
}

find()에서 경로 압축을 쓰면 union 연산이 사실상 O(1)이 되어 전체 시간복잡도는 O(ElogE)가 된다.

알고리즘시간복잡도핵심 자료구조
크루스칼O(ElogE)Disjoint Set + 간선 정렬
프림O(ElogV)PriorityQueue + visited

14. 오늘 리뷰

오늘 빵집 문제에서 visited 복원 없음이 핵심이었다. BackTracking의 기본인 "선택 해제"를 의도적으로 생략했다. 실패한 경로는 다른 출발점에서도 실패한다는 문제의 특성 덕분이다.

알고리즘 패턴을 기계적으로 외우면 안 된다는 걸 다시 느꼈다. "왜 이 패턴이 맞는가"를 문제의 특성에서 찾아야 한다.

크루스칼에서 Disjoint Set이 사이클 감지를 O(1)에 가깝게 해준다는 것도 인상 깊었다. 자료구조가 알고리즘의 성능을 결정한다는 게 오늘도 반복됐다.

15. 키워드 정리

다익스트라 완전 이진 트리 MST 크루스칼

16. 내일의 목표

  • 프림 알고리즘
  • 코테
profile
Soohwan Lim
developer
이전 포스트

[LG U+ 유레카 4기] WEEK 04 - 알고리즘 (9)

다음 포스트

[LG U+ 유레카 4기] WEEK 04 - 알고리즘 (11)

0개의 댓글