DFS, BFS

오태준태오·2025년 4월 27일

CodingTest

목록 보기

12/12

인접 리스트란?

그래프를 표현하는 방법에는 크게 두 가지가 있다.

인접 행렬 (Adjacency Maxtrix)
2차원 배열을 사용해서 노드 간 연결 상태를 저장
인접 리스트 (Adjacency List)
각 정점 (Vertex)마다 "연결된 정점들의 리스트"를 따로 관리

인접 행렬

구현 시에 2차원 배열 (int [][])로 노드 간 연결 여부를 저장한다.
만약 정점의 수가 N개면 N x N 크기의 배열을 사용한다.
해당 연결의 방향성을 표시할 수 있어 큰 장점이 있으나, 모든 노드 간의 관계를 저장해야하기 때문에 연결이 적어도 공간 낭비가 심하게 작용된다.

int[][] graph = {
    {0, 1, 1, 0},
    {0, 0, 1, 0},
    {1, 0, 0, 1},
    {0, 0, 0, 0}
};

인접 리스트

정점별 연결된 리스트를 따로 관리한다.
메모리는 신제 연결된 간선 수만 사용하기 때문에 인접 행렬보다 효율적이다.
연결이 적은 상황에서 굉장히 요율적이다.

List<List<Integer>> graph = new ArrayList<>();
graph.add(Arrays.asList(1, 2));
graph.add(Arrays.asList(2));
graph.add(Arrays.asList(0, 3));
graph.add(Arrays.asList());

어떤 상황에서?

인접행렬은 노드 수가 적고, 간선이 많을 경우
인접리스트는 노드 수가 많고, 간선이 적을 경우 사용한다.

즉, DFS, BFS의 경우처럼 "연결된 노드" 사이만을 순회하는 알고리즘은 보통 인접 리스트로 구현한다.

DFS VS BFS

이러한 탐색 방식은 크게 깊이와 너비라는 두가지 방식으로 나뉜다.

DFS

깊이 우선 탐색은 Depth-First Search의 약어로, 한 방향으로 끝까지 탐색하고 막히면 돌아와 다른 방향을 탐색하는 방식이다.
재귀를 사용하며 visited 배열을 생성하여 방문한 노드를 다시 방문하지 않도록 한다.
재귀를 사용하는 만큼 깊이가 너무 깊어진다면 성능이 너무 떨어진다.

    private void dfs(List<List<Integer>> graph, boolean[] visited, int current){
        visited[current] = true;
        
        for (int next : graph.get(current)) {
            if (!visited[next]) {
                dfs(graph, visited, next);
            }
        }
    }

해당 코드는 내가 DFS 구현 시 사용하는 탬플릿이다.

BFS

너비 우선 탐색은 Breadth-First Search의 약어로, 현재 노드에 인접한 모든 노드를 먼저 탐색하고, 그 다음 단계로 넘어가는 방식이다.

public void bfs(List<List<Integer>> graph, int startVertex, boolean[] visited, int[] distance) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startVertex);
        visited[startVertex] = true;

        while (!queue.isEmpty()) {
            int curVertex = queue.poll();

            for (int nextVertex : graph.get(curVertex)) {
                if (!visited[nextVertex]) {
                    queue.add(nextVertex);
                    visited[nextVertex] = true;
                }
            }
        }
    }

해당 코드는 내가 BFS를 구현할 때 사용하는 탬플릿이다.