[Java] BFS, DFS를 Java로 구현해보자

자바로 그래프 구현하기

그래프를 구현하기 위해, 각 노드의 데이터와 다른 노드와의 연결 정보를 가질 수 있는 Node 클래스를 직접 만들어 보겠습니다.

1. Node 클래스 정의하기

노드는 고유한 데이터(예: 이름)를 가지며, 어떤 노드들과 연결되어 있는지에 대한 목록을 가집니다. 또한, 그래프 탐색 시 이미 방문한 노드인지를 확인하기 위한 상태 값도 필요합니다.

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class Node {
    private String name; // 노드의 이름
    private List<Node> links; // 연결된 노드 목록
    private boolean visited; // 방문 여부

    public Node(String name) {
        this.name = name;
        this.links = new ArrayList<>();
    }

    // 다른 노드와 연결
    public void link(Node node) {
        links.add(node);
    }

    // 방문 여부 확인 및 설정
    public boolean isVisited() {
        return visited;
    }

    public void visit() {
        this.visited = true;
    }

    // Getter, toString, equals, hashCode 등
    // ... (생략)
}

• name: 노드를 식별하기 위한 데이터입니다.
• links: 현재 노드와 직접 연결된 다른 Node 객체들의 리스트입니다.
• visited: 탐색 알고리즘에서 중복 방문을 방지하기 위한 플래그입니다.

 

2. 그래프 생성 및 노드 연결하기

정의한 Node 클래스를 사용하여 각 노드 객체를 생성하고, link() 메서드를 통해 서로 연결하여 그래프를 구성합니다.

예를 들어, 아래와 같은 구조의 그래프를 만든다고 가정해 봅시다.

• A는 B, D와 연결
• B는 A, C, E와 연결
• C는 B, D와 연결
• D는 A, C, E와 연결
• E는 B, D와 연결

// 1. 노드 생성
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");

// 2. 노드 간 연결 (양방향)
a.link(b); a.link(d);
b.link(a); b.link(c); b.link(e);
c.link(b); c.link(d);
d.link(a); d.link(c); d.link(e);
e.link(b); e.link(d);

---

그래프 탐색 알고리즘

그래프의 모든 노드를 방문하는 방법에는 크게 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 두 가지가 있습니다.

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

BFS는 시작 노드에서 가장 가까운 노드들부터 차례대로 탐색하는 방식입니다.

이 알고리즘은 큐(Queue) 자료구조를 사용하여 다음에 방문할 노드 목록을 관리합니다.

 

구현 로직

1. 시작 노드를 큐에 추가하고 방문 처리합니다.
2. 큐가 비어있지 않은 동안 다음을 반복합니다.
   • 큐에서 노드를 하나 꺼냅니다.
   • 만약 이 노드가 찾고자 하는 노드라면 탐색을 종료합니다.
   • 꺼낸 노드와 연결된 모든 노드를 확인합니다.
   • 아직 방문하지 않았고, 큐에 들어있지 않은 노드를 큐에 추가하고 방문 처리합니다.

import java.util.LinkedList;
import java.util.Queue;

public void bfs(Node startNode, String targetName) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(startNode);
    startNode.visit();

    while (!queue.isEmpty()) {
        Node currentNode = queue.poll();
        System.out.println("방문: " + currentNode.getName());

        if (currentNode.getName().equals(targetName)) {
            System.out.println(targetName + " 찾음!");
            return;
        }

        for (Node neighbor : currentNode.getLinks()) {
            if (!neighbor.isVisited()) {
                neighbor.visit();
                queue.add(neighbor);
            }
        }
    }
}

A에서 시작하여 E를 찾는 경우, BFS는 A → B → D → C → E 순서로 노드를 방문하여 목표를 찾아냅니다.

---

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

DFS는 시작 노드에서 한 방향으로 최대한 깊게 들어간 후, 더 이상 갈 곳이 없으면 이전 노드로 돌아와 다른 경로를 탐색하는 방식입니다. 이 알고리즘은 스택(Stack) 자료구조를 사용하여 방문할 노드 목록을 관리합니다.

구현 로직
BFS와 거의 동일하지만, 큐 대신 스택을 사용한다는 점이 다릅니다.

1. 시작 노드를 스택에 추가합니다.
2. 스택이 비어있지 않은 동안 다음을 반복합니다.
   • 스택에서 노드를 하나 꺼내고 방문 처리합니다.
   • 만약 이 노드가 찾고자 하는 노드라면 탐색을 종료합니다.
   • 꺼낸 노드와 연결된 모든 노드를 확인합니다.
   • 아직 방문하지 않은 노드를 스택에 추가합니다.

import java.util.Stack;

public void dfs(Node startNode, String targetName) {
    Stack<Node> stack = new Stack<>();
    stack.push(startNode);

    while (!stack.isEmpty()) {
        Node currentNode = stack.pop();

        if (currentNode.isVisited()) continue;

        currentNode.visit();
        System.out.println("방문: " + currentNode.getName());

        if (currentNode.getName().equals(targetName)) {
            System.out.println(targetName + " 찾음!");
            return;
        }

        for (Node neighbor : currentNode.getLinks()) {
            if (!neighbor.isVisited()) {
                stack.push(neighbor);
            }
        }
    }
}

A에서 시작하여 E를 찾는 경우, DFS는 스택에 노드가 추가되는 순서에 따라 탐색 경로가 달라집니다. 예를 들어, A → D → E 순서로 더 빠르게 목표를 찾을 수 있습니다.

---

BFS vs. DFS

구분	너비 우선 탐색 (BFS)	깊이 우선 탐색 (DFS)
자료구조	큐 (Queue)	스택 (Stack)
탐색 경로	시작점에서 가까운 순서대로 넓게 탐색	한 경로를 따라 최대한 깊게 탐색
특징	최단 경로를 찾는 데 유리	모든 노드를 방문해야 할 때 유리

 

BFS와 DFS는 탐색 순서에만 차이가 있을 뿐, 어느 방식이 절대적으로 더 좋다고 말할 수는 없습니다.

문제의 특성에 따라 적합한 탐색 방식을 선택하는 것이 중요합니다.

---

정리

• 탐색 알고리즘:
  • BFS는 큐를 사용하여 가까운 노드부터 탐색합니다.
  • DFS는 스택을 사용하여 깊은 노드부터 탐색합니다.
• 핵심: 두 방식 모두 탐색 시 중복을 피하기 위해 방문 여부를 반드시 확인해야 합니다.

직접 Node 클래스를 만들고 그래프를 구성한 후, BFS와 DFS를 모두 구현해보면서 각 알고리즘의 동작 원리를 익히는 것이 중요합니다.