그래프와 탐색 — BFS, DFS 그리고 면접에서의 활용

트리는 사이클이 없는 연결 그래프의 특수한 형태입니다. 그렇다면 사이클이 있고, 방향이 있고, 가중치가 있는 일반적인 그래프는 어떻게 표현하고 탐색할까요?

그래프(Graph) 는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 트리와 달리 사이클과 방향을 가질 수 있습니다. 미로 탐색, 최단 경로, 위상 정렬 등 다양한 문제의 기반이 되며, BFS와 DFS라는 두 가지 핵심 탐색 전략으로 풀어갑니다.

그래프 기본 용어

그래프 표현: 인접 행렬 vs 인접 리스트

인접 행렬

2차원 배열로 표현합니다. matrix[i][j] = 1이면 i에서 j로 간선이 존재합니다.

int[][] matrix = new int[5][5];
matrix[0][1] = 1;  // 0 → 1 간선
matrix[1][0] = 1;  // 무방향이면 양쪽 표시

인접 리스트

각 정점마다 연결된 정점 목록을 리스트로 관리합니다.

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < 5; i++) adj.add(new ArrayList<>());
adj.get(0).add(1);  // 0 → 1
adj.get(0).add(3);  // 0 → 3

선택 기준

정점이 10만 개인데 인접 행렬을 만들면 10만 x 10만 = 100억 칸으로, 메모리 초과가 발생합니다. 대부분의 경우 ** 인접 리스트 **를 사용합니다.

BFS -- 너비 우선 탐색

BFS는 시작 정점에서 ** 가까운 정점부터** 탐색합니다. Queue를 사용하여, 현재 정점의 이웃을 모두 큐에 넣고, 큐에서 하나 꺼내서 그 이웃을 또 넣는 과정을 반복합니다.

void bfs(List<List<Integer>> adj, int start) {
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int cur = queue.poll();
        for (int next : adj.get(cur)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

BFS의 핵심 특성:

1. ** 최단 경로 보장 **: 가중치가 없는 그래프에서 BFS로 처음 도달한 경로가 곧 최단 경로입니다. 가까운 정점부터 방문하기 때문입니다.
2. ** 레벨별 탐색 **: 큐의 크기를 기준으로 레벨을 구분할 수 있습니다. queue.size()를 레벨 시작 시점에 저장하면, 같은 레벨의 정점만 처리할 수 있습니다.
3. 시간 복잡도: O(V + E) -- 모든 정점과 간선을 한 번씩 방문합니다.

DFS -- 깊이 우선 탐색

DFS는 하나의 경로를 ** 끝까지 파고든** 뒤, 막다른 길에 도달하면 되돌아와서 다른 경로를 탐색합니다.

재귀 구현

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

직관적이고 코드가 짧지만, 정점이 많으면 스택 오버플로 위험이 있습니다.

명시적 스택 구현

재귀 대신 Stack을 직접 사용합니다.

void dfsStack(List<List<Integer>> adj, int start) {
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int cur = stack.pop();
        if (visited[cur]) continue;
        visited[cur] = true;

        List<Integer> neighbors = adj.get(cur);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            if (!visited[neighbors.get(i)])
                stack.push(neighbors.get(i));
        }
    }
}

인접 정점을 ** 역순으로** 넣어야 작은 번호부터 탐색됩니다.

DFS의 핵심 특성:

1. ** 경로 탐색 **: "A에서 B까지 경로가 존재하는가?" 같은 질문에 적합합니다.
2. ** 사이클 탐지 **: 방향 그래프에서는 방문 상태를 3단계(미방문/방문 중/방문 완료)로 나누어, 방문 중인 노드를 다시 만나면 사이클로 판별합니다.
3. ** 백트래킹 **: DFS의 "되돌아가기" 성질을 이용한 탐색 기법. 조합/순열 문제의 기본입니다.

BFS vs DFS 선택 기준

"최단"이 보이면 BFS, "모든 경로" 또는 "사이클"이 보이면 DFS를 먼저 떠올리면 됩니다.

위상 정렬 (Topological Sort)

위상 정렬은 ** 방향 비순환 그래프(DAG)**에서 선후 관계를 유지하며 정점을 일렬로 나열하는 것입니다. "이 과목을 듣기 전에 저 과목을 먼저 들어야 한다" 같은 의존 관계를 순서대로 정리할 때 사용합니다.

BFS 기반의 Kahn's Algorithm이 대표적입니다. 핵심 아이디어는 ** 진입 차수가 0인 정점 **부터 결과에 넣고, 해당 정점의 간선을 제거하여 새로운 진입 차수 0 정점을 만드는 것입니다.

진입 차수를 계산하고 큐에 넣는 부분입니다.

int[] inDegree = new int[n];
for (int i = 0; i < n; i++)
    for (int next : adj.get(i))
        inDegree[next]++;

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++)
    if (inDegree[i] == 0) queue.offer(i);

큐에서 꺼내면서 인접 정점의 진입 차수를 줄이고, 0이 되면 큐에 추가합니다.

List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
    int cur = queue.poll();
    result.add(cur);
    for (int next : adj.get(cur)) {
        if (--inDegree[next] == 0)
            queue.offer(next);
    }
}
// result.size() != n이면 사이클 존재

사이클이 있으면 진입 차수가 0이 되는 정점이 중간에 사라지므로, 모든 정점을 처리하지 못합니다. result.size() != n이면 사이클이 존재한다는 뜻입니다.

최단 경로 알고리즘 선택

가중치 유무에 따라 알고리즘이 달라집니다.

다익스트라가 음수 가중치를 처리할 수 없는 이유는 그리디 방식 때문입니다. 현재 최단 거리인 정점을 확정하는데, 음수 간선이 있으면 이미 확정된 거리가 나중에 더 짧아질 수 있어 정확한 결과를 보장하지 못합니다. 벨만포드는 DP 기반으로 모든 간선을 반복 갱신하여 이 문제를 해결합니다.

주의할 점

인접 행렬의 메모리 폭발

정점이 V개일 때 인접 행렬은 O(V^2) 메모리를 사용합니다. 정점 100,000개면 약 40GB의 메모리가 필요합니다. 밀집 그래프가 아닌 이상 인접 리스트를 사용해야 합니다.

DFS 재귀 깊이 제한

Java의 기본 스택 크기로는 약 5,000~10,000 깊이의 재귀가 한계입니다. 정점 수가 이보다 많으면 명시적 스택을 사용하거나, JVM 옵션으로 스택 크기를 늘려야 합니다(-Xss).

무방향 그래프의 사이클 탐지

무방향 그래프에서 DFS로 사이클을 탐지할 때, 바로 직전에 방문한 부모 노드를 "방문 중"으로 오판하지 않도록 ** 부모 노드를 별도로 추적 **해야 합니다. 부모가 아닌 이미 방문한 노드를 만났을 때만 사이클입니다.

BFS에서 visited 체크 시점

BFS에서 visited를 ** 큐에 넣을 때** 체크하는 것과 ** 큐에서 꺼낼 때** 체크하는 것은 결과가 다릅니다. 큐에 넣을 때 체크하지 않으면 같은 정점이 큐에 여러 번 들어가서 메모리가 낭비되고, 최단 경로 보장도 깨질 수 있습니다.

정리