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

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

유레카부트캠프

목록 보기
16/31
post-thumbnail

BFS, DFS - 그래프 탐색

1. 오늘의 학습 흐름

  • BFS(너비 우선 탐색) 동작 원리 및 구현
  • DFS(깊이 우선 탐색) 동작 원리 및 구현
  • Tree vs Graph 비교
  • 인접 행렬 메모리 이슈
  • 정올 1661 미로 탈출 로봇 (BFS, DFS 두 가지 풀이)
  • BFS vs DFS 언제 쓰는가

2. Tree vs Graph 비교

관계방향Cycle방문 체크
Tree1:N단방향XX
GraphN:M양방향/무방향OO

그래프는 사이클이 있을 수 있어서 방문 체크가 필수다. 트리는 사이클이 없으니까 visited 없이도 탐색이 가능하다.

3. 인접 행렬 메모리 문제

인접 행렬은 V×V 크기의 2차원 배열이라 정점 수가 늘어나면 메모리가 급격히 증가한다.

정점 수인접행렬 크기수행 횟수메모리
1,0001,000,0001,000,0004MB
2,0004,000,0004,000,00016MB

정점이 2배가 되면 메모리는 4배가 된다. 정점이 많고 간선이 적은 희소 그래프(Sparse Graph)라면 인접 리스트가 훨씬 유리하다.

4. BFS (Breadth First Search) - 너비 우선 탐색

시작 정점에서 인접한 정점들을 먼저 모두 방문한 후, 방문한 정점을 시작점으로 다시 인접 정점들을 차례로 방문하는 방식이다. Queue를 사용한다.

BFS 동작 순서

① 시작 Node를 Queue에 넣기, 방문 체크
② Queue가 isEmpty()가 될 때까지 반복
③ Queue에서 Node 꺼내기
④ 인접 Node를 Queue에 추가, 방문 체크

BFS 기본 코드 틀

static boolean[] visited;
static int[][] adjMatrix;  // 인접 행렬

public static void bfs(int start) {
    Queue<Integer> queue = new ArrayDeque<>();
    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int curr = queue.poll();
        // curr에서 할 일 (task)
        System.out.print(curr + " ");

        for (int next = 0; next < N; next++) {
            if (adjMatrix[curr][next] == 1 && !visited[next]) {
                visited[next] = true;    // 큐에 넣기 전에 방문 체크!
                queue.offer(next);
            }
        }
    }
}

방문 체크를 큐에 넣을 때 해야 한다. 꺼낼 때 하면 같은 노드가 큐에 중복으로 들어갈 수 있다.

시간복잡도: O(V + E) - 인접 리스트 기준, O(V²) - 인접 행렬 기준

5. DFS (Depth First Search) - 깊이 우선 탐색

시작 정점에서 한 방향으로 계속 깊이 탐색하다가 더 갈 수 없으면 되돌아와서 다른 경로를 탐색하는 방식이다. Stack 또는 재귀를 사용한다.

DFS 동작 순서

① 방문한 Node를 Stack에 추가
② Stack에서 Node 꺼내서 탐색
③ 방문 체크
④ 인접 방문

DFS 기본 코드 틀 (재귀)

static boolean[] visited;
static int[][] adjMatrix;

public static void dfs(int curr) {
    visited[curr] = true;
    System.out.print(curr + " ");  // task

    for (int next = 0; next < N; next++) {
        if (adjMatrix[curr][next] == 1 && !visited[next]) {
            dfs(next);
        }
    }
}
// 호출: dfs(시작 정점)

시간복잡도: O(V + E)

6. 정올 1661 - 미로 탈출 로봇

시작점에서 도착점까지 최단 거리를 구하는 문제다. 세 가지 버전으로 풀었다.

DFS 버전 1 - visited + 가지치기 (시간 초과)

static boolean[][] visited;
static int min = Integer.MAX_VALUE;

private static void dfs(int r, int c, int dist) {
    if (r == erow && c == ecol) {
        min = Math.min(min, dist);
        return;
    }
    if (dist >= min) return;  // 가지치기: 현재 거리가 이미 최솟값 이상이면 종료

    for (int[] dir : direction) {
        int nr = r + dir[0];
        int nc = c + dir[1];
        if (nr >= 0 && nr < rowN && nc >= 0 && nc < colN
            && map[nr][nc] == 0 && !visited[nr][nc]) {
            visited[nr][nc] = true;
            dfs(nr, nc, dist + 1);
            visited[nr][nc] = false;  // BackTracking: 선택 해제
        }
    }
}

최악의 경우 모든 경로를 다 탐색해서 시간 초과가 난다.

DFS 버전 2 - 거리를 map에 저장 (시간 통과)

visited 배열 대신 map 자체에 이동 거리를 저장한다. 같은 위치를 더 긴 거리로 다시 방문하면 skip한다.

// visited 배열 없음, map에 거리 저장
private static void dfs(int r, int c) {
    if (r == erow && c == ecol) return;

    int dist = map[r][c];
    for (int[] dir : direction) {
        int nr = r + dir[0];
        int nc = c + dir[1];
        if (nr >= 0 && nr < rowN && nc >= 0 && nc < colN
            && (map[nr][nc] == 0         // 아직 안 간 길
                || map[nr][nc] > dist + 1)) {  // 더 짧은 경로 발견 시 재방문
            map[nr][nc] = dist + 1;
            dfs(nr, nc);
        }
    }
}
// 시작점: map[srow][scol] = 1 (0과 구분하기 위해 1부터)
// 결과: map[erow][ecol] - 1

map[nr][nc] > dist + 1 조건이 핵심이다. 이전에 방문했더라도 지금 경로가 더 짧으면 다시 탐색한다. 이전 경로보다 길면 앞으로 갈 모든 경로도 더 길 것이 자명하므로 skip한다.

BFS 버전 - 가장 적합한 풀이

public static void bfs(int r, int c) {
    Queue<int[]> queue = new ArrayDeque<>();
    map[r][c] = 1;  // 시작점 1로 설정
    queue.offer(new int[]{r, c});

    L: while (!queue.isEmpty()) {
        int[] temp = queue.poll();
        int count = map[temp[0]][temp[1]];

        for (int i = 0; i < 4; i++) {
            int nr = temp[0] + dr[i];
            int nc = temp[1] + dc[i];
            if (nc >= 0 && nc < colN && nr >= 0 && nr < rowN
                && map[nr][nc] == 0) {       // 0이면 아직 안 간 길 (자동 방문 체크)
                map[nr][nc] = count + 1;     // 이동 거리를 map에 저장
                if (nr == erow && nc == ecol) break L;  // 도착하면 즉시 종료
                queue.offer(new int[]{nr, nc});
            }
        }
    }
}
// 결과: map[erow][ecol] - 1

BFS는 가중치 없는 그래프에서 처음 도착했을 때가 항상 최단 거리임이 보장된다. 도착점에 처음 도달한 순간 바로 종료해도 된다.

map에 거리를 저장하면 visited 배열 없이도 방문 체크가 된다. 0이 "아직 안 간 길"이고, 1 이상이 "이미 방문한 거리"다.

7. BFS vs DFS 언제 쓰는가

BFSDFS
자료구조QueueStack / 재귀
최단 거리O - 가중치 없는 최단 거리에 최적X - 모든 경로 탐색 필요
경우의 수XO - 경로의 모든 경우 탐색
시간복잡도O(V+E)O(V+E), 최악 O(V!)

BFS를 써야 하는 경우:

  • A → B 가중치 없는 최단 거리 구하기 → O(V)으로 가장 빠름
  • 특정 지점에서 조금씩 퍼져나가는 문제

DFS를 써야 하는 경우:

  • A → B까지 갈 수 있는 경로의 경우의 수 구하기
  • N이 작거나, 8×8처럼 길막이 많은 경우 (16×16 가능, 그 이상은 DP)
  • 특정 지점에서 길을 따라 계속 가야 하는 문제

가중치 있는 최단 거리 문제는 다익스트라 알고리즘으로 풀어야 한다. O(N²) 또는 O(ElogV).

미로 문제에서 DFS가 시간 초과가 나는 이유: DFS는 모든 경로를 전부 탐색하는 O(N!)에 가까운 최악 케이스가 있다. BFS는 처음 도달했을 때가 최단 거리라서 O(N)으로 끝난다.

8. 오늘 후기

오늘 같은 문제를 DFS 2개, BFS 1개로 풀면서 알고리즘 선택이 얼마나 중요한지 체감했다.

DFS 버전 1은 시간 초과, DFS 버전 2는 map에 거리 저장으로 통과, BFS는 깔끔하게 통과. 코드 복잡도는 DFS 버전 2가 제일 까다로웠다.

최단 거리 문제는 BFS가 정답이다. DFS로 최단 거리를 구하려면 가지치기를 정교하게 설계해야 하고 그래도 시간 초과 위험이 있다. BFS는 첫 도달 = 최단 거리라는 수학적 보장이 있기 때문이다.

BackTracking은 다음 주에 배운다. DFS + 가지치기의 정제된 버전이라 이번 주 내용이 기반이 된다.

9. 키워드 정리

BFS DFS

10. 내일의 목표

  • GSAT 마무리
  • 또 코테 준비
  • Petfit 설계 마무리
profile
Soohwan Lim
developer
이전 포스트

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

다음 포스트

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

0개의 댓글