그래프란?

그래프는 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 구성된 자료 구조입니다. 그래프는 다양한 형태로 표현될 수 있으며, 현실 세계의 다양한 문제를 모델링하는 데에 사용됩니다. 예를 들면, 소셜 네트워크에서 사람들을 노드로 표현하고, 친구 관계를 간선으로 표현할 수 있습니다.

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

DFS(깊이 우선 탐색)는 그래프의 시작 노드에서부터 가능한 한 깊게 탐색한 후, 더 이상 탐색할 수 없을 때 이전 단계로 돌아와 다른 경로를 탐색합니다. DFS는 스택(Stack)이나 재귀 함수를 사용하여 구현할 수 있습니다. DFS는 미로 찾기, 그래프의 연결 여부 확인, 트리 순회 등 다양한 문제에 활용됩니다.

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

BFS(너비 우선 탐색)는 그래프의 시작 노드에서부터 인접한 노드를 먼저 탐색하고, 해당 인접 노드들을 모두 방문한 후에는 그 다음 단계의 인접 노드들을 탐색합니다. BFS는 큐(Queue)를 사용하여 구현할 수 있습니다. BFS는 최단 경로 탐색, 네트워크 패킷 전송 등에 활용됩니다.

DFS와 BFS의 차이점

DFS (깊이 우선 탐색)

• 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다.
• 시작 노드에서부터 가능한 한 깊게 탐색합니다.
• 더 이상 진행할 수 없을 때 이전 단계로 돌아와 다른 경로를 탐색합니다.
• 깊은 단계를 우선적으로 탐색합니다.
• 스택을 사용하기 때문에 최근에 방문한 노드를 먼저 탐색합니다.

BFS (너비 우선 탐색)

• 큐(Queue)를 사용하여 구현할 수 있습니다.
• 시작 노드에서부터 인접한 노드를 먼저 탐색합니다.
• 해당 인접 노드들을 모두 방문한 후에는 그 다음 단계의 인접 노드들을 탐색합니다.
• 너비를 우선적으로 탐색합니다.
• 큐를 사용하기 때문에 먼저 방문한 노드를 먼저 탐색합니다.

시간 복잡도

N은 노드, E는 간선일 때

인접 리스트 : O(N+E)
인접 행렬 : O(N²)

일반적으로 E(간선)의 크기가 N²에 비해 상대적으로 적기 때문에
인접 리스트 방식이 효율적임

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.

2) 경로의 특징을 저장해둬야 하는 문제

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

3) 최단거리 구해야 하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

DFS 코드

• 입력

7 5 1 //노드 수, 간선 수, 시작 인덱스
1 2
1 3
3 4
4 5
5 7

• 출력

1 2 3 4 5 7

import java.util.*;

class Main {
    static ArrayList<Integer>[] graph;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int nodes = scanner.nextInt();
        int edges = scanner.nextInt();
        int startIndex = scanner.nextInt();

        // 그래프 초기화
        graph = new ArrayList[nodes + 1];
        for (int i = 1; i <= nodes; i++) {
            graph[i] = new ArrayList<>();
        }

        visited = new boolean[nodes + 1];

        // 간선 정보 입력 받기
        for (int i = 0; i < edges; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }

        // DFS 호출
        dfs(startIndex);

        scanner.close();
    }

    static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int nextNode : graph[node]) {
            if (!visited[nextNode]) {
                dfs(nextNode);
            }
        }
    }
}

BFS 코드

• 입력

7 5 1 //노드 수, 간선 수, 시작 인덱스
1 2
1 3
3 4
4 5
5 7

• 출력

1 2 3 4 5 7

import java.util.*;

class Main {
    static ArrayList<Integer>[] graph;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int nodes = scanner.nextInt();
        int edges = scanner.nextInt();
        int startIndex = scanner.nextInt();

        // 그래프 초기화
        graph = new ArrayList[nodes + 1];
        for (int i = 1; i <= nodes; i++) {
            graph[i] = new ArrayList<>();
        }

        visited = new boolean[nodes + 1];

        // 간선 정보 입력 받기
        for (int i = 0; i < edges; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }

        // BFS 호출
        bfs(startIndex);

        scanner.close();
    }

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

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int nextNode : graph[node]) {
                if (!visited[nextNode]) {
                    queue.offer(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
    }
}