그래프 탐색 (Graph Search): 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

먼저, 탐색을 하기 위해서는 지도(Graph)가 필요하다.

1. 그래프(Graph)란?

• 점(Node / Vertex): 도시, 사람, 데이터.
• 선(Edge): 도로, 친구 관계, 연결 선.

그래프를 나타낸 이미지

 

컴퓨터에게 이 지도를 알려주는 방법은 딱 2가지가 존재한다. 코딩테스트에 있어서는 2번(리스트) 방식을 많이 사용한다.

 

1.1. 2차원 배열(Adjacency Matrix)

• 방식: 엑셀 표처럼 모든 연결 관계를 1(연결됨)과 0(안됨)으로 표시하는 방법.
• 장점: graph[1][2]가 연결됐는지에 대한 확인이 빠르다.
• 단점: 점이 10,000개라면 표가 너무 커져서 메모리가 터진다.

 

1.2. 연결 리스트(Adjacency List)

• 방식: 각 점마다 자신과 연결된 애들만 나열한다.
• 장점: 필요한 것만 저장해서 메모리를 절약할 수 있다.

---

 

2. DFS (깊이 우선 탐색) : 불도저

"한 우물만 판다."

깊이 우선 탐색의 예시 (출처: 위키백과)

갈림길이 나오면 무조건 한쪽으로 끝까지 들어간다. 막다른 골목에 다다르면 그제서야 뒤로 돌아 나와 다른 길을 찾는 탐색 방법이다.

• 핵심 도구: 재귀 함수(Recursion) 또는 스택(Stack)
• 순서: 1 → 2 → 4 → 5 (끝 찍고) → 3 ...
• 예시: 이진 트리(Binary Tree) 순회 방식이 이 깊이 우선 방식에 속한다.
  • preOrder, inOrder, postOrder
• 특징
  • 모든 경우의 수를 탐색해야할 때 유리하다.
  • 단, 찾은 경로가 최단 경로라는 보장은 없다.

 

 

3. BFS (너비 우선 탐색) : 와이파이

주변부터 챙긴다.

너비 우선 탐색의 예시 (출처: 위키백과)

 

나랑 가까운 곳부터 다 방문하고, 그 다음에 가까운곳을 방문한다. 와이파이 신호가 퍼지듯이 층층이 퍼져나가는 형태다.

• 핵심 도구: 큐(Queue). 줄세우기
• 순서: 1 → 2 → 3 (주변 다 확인 후) → 4 → 5 ...
• 특징
  • 최단 경로를 찾을 때 매우 강력하다. (가중치가 없는 그래프에서)

 

4. 구현

package graph_search;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Study_DFS_BFS {

    static class Graph { // 그래프
        class Node {
            int data; // node의 데이터
            LinkedList<Node> adjacent; // 인접한 노드들의 리스트
            boolean marked; // 해당 노드를 방문했는지에 대한 정보

            // 노드 생성 시
            Node (int data) {
                this.data = data;
                this.marked = false;
                adjacent = new LinkedList<Node>();
            }
        }

        Node[] nodes;

        Graph(int size) {
            nodes = new Node[size];

            for (int i = 0; i < size; i++) {
                nodes[i] = new Node(i);
            }
        }

        // 두 노드의 연결선
        void addEdge(int i1, int i2) {
            Node n1 = nodes[i1];
            Node n2 = nodes[i2];

            // n1 노드에 n2 노드가 있는지 확인하고 없다면 추가
            if (!n1.adjacent.contains(n2)) {
                n1.adjacent.add(n2);
            }

            // 반대로 n2 노드에 n1 노드가 있는지 확인하고 없다면 추가
            if (!n2.adjacent.contains(n1)) {
                n2.adjacent.add(n1);
            }
        }

        void dfs() {
            dfs(0);
        }

        void dfs(int index) {
            Node root = nodes[index];
//            Stack<Node> stack = new Stack<Node>(); // stack 클래스는 매우 비효율적임
            Deque<Node> stack = new ArrayDeque<>();
            stack.push(root);
            root.marked = true;

            while(!stack.isEmpty()) {
                // 먼저 스택에 들어있는 가장 맨위의 노드를 꺼낸다.
                Node r = stack.pop();

                // Stack에 추가되지 않은 인접한 노드들만 추가하는 작업
                for (Node n : r.adjacent) {
                    if (!n.marked) { // 아직 Stack에 들어오지 않았다면
                        n.marked = true; // 해당 인접 노드 마커 변경
                        stack.push(n); // 스택에 추가
                    }
                }

                // 꺼낸 노드를 출력한다.
                visit(r);
            }
        }

        // 재귀함수를 이용한 dfs
        void dfsR(Node r) {
            if (r == null) return;
            r.marked = true;
            visit(r);
            for (Node n : r.adjacent) {
                // 아직 호출되지 않은 인접노드라면 재귀함수를 이용해서 호출한다.
                if (!n.marked) {
                    dfsR(n);
                }
            }
        }

        void dfsR(int index) {
            dfsR(nodes[index]);
        }

        void dfsR() {
            dfsR(nodes[0]);
        }

        void bfs() {
            bfs(0);
        }

        void bfs(int index) {
            Node root = nodes[index];
            Queue<Node> queue = new ArrayDeque<>();
            queue.offer(root);
            root.marked = true;

            while (!queue.isEmpty()) {
                Node r = queue.poll();
                // 출력한 노드의 인접 노드를 큐에 추가한다.
                for (Node n : r.adjacent) {
                    if (!n.marked) {
                        n.marked = true;
                        queue.offer(n);
                    }
                }

                visit(r);
            }
        }

        // 방문
        void visit(Node n) {
            System.out.print(n.data + " ");
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(9);

        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(5, 6);
        g.addEdge(5, 7);
        g.addEdge(6, 8);

//        g.dfs(3);
//        g.dfsR(3);
//        g.bfs();
    }
}