[1260] DFS와 BFS

개요

[백준 1260]
https://www.acmicpc.net/problem/1260

정점과 간선을 이어 만든 그래프를 탐색하는 문제이다.

사용자에게 입력을 받아 그래프를 연결하고 DFS와 BFS를 함수로 구현하여 문제를 해결하였다.

---

⭐️ 깊이 우선 탐색 (DFS, Dreadth-First Search)

DFS는 스택(Stack) 또는 재귀(Recursion) 를 이용하여 한 방향으로 탐색을 계속 진행하는 방식이다.

DFS 탐색 과정

1. 시작 정점을 방문하고 출력한다.
2. 현재 정점과 연결된 정점들을 작은 번호부터 탐색한다.
3. 방문하지 않은 정점이면 재귀적으로 탐색을 이어간다.
   
   

DFS 코드

public static void DFS(int cur) {
    System.out.print(cur + " ");  // 현재 노드 출력
    vis[cur] = true;              // 방문 처리

    for (int nxt : adj[cur]) {    // 연결된 노드 탐색
        if (!vis[nxt]) {          // 방문하지 않았다면 재귀 호출
            DFS(nxt);
        }
    }
}

---

⭐️ 넓이 우선 탐색 (BFS, Breadth-First Search)

BFS는 큐(Queue) 를 이용하여 가까운 노드부터 탐색하는 방식이다.

BFS 탐색 과정

1. 시작 정점을 큐에 넣고 방문 처리한다.
2. 큐에서 정점을 하나 꺼내 출력한다.
3. 현재 정점과 연결된 정점들을 작은 번호부터 탐색한다.
4. 방문하지 않은 정점이면 큐에 추가하고 방문 처리한다.
5. 큐가 빌 때까지 반복한다.
   
   

BFS 코드

public static void BFS(int start) {
    Queue<Integer> q = new LinkedList<>();
    q.add(start);
    vis[start] = true;

    while (!q.isEmpty()) {
        int cur = q.poll();  // 큐에서 하나 꺼내기
        System.out.print(cur + " ");

        for (int nxt : adj[cur]) {
            if (!vis[nxt]) { // 방문하지 않았다면 큐에 추가
                vis[nxt] = true;
                q.add(nxt);
            }
        }
    }
}

---

⭐️ 그래프 표현

그래프를 구현하기 위해서 인접 리스트를 사용하여 연결 여부를 저장하였다.

그래프 초기화를 위한 코드는 아래와 같다.

adj = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
    adj[i] = new ArrayList<>();
}

또한, 입력을 받아 양방향으로 간선을 연결하고 인접한 값 중 오름차순으로 탐색하기에 오름차순으로 정렬 과정이 필요하다.

for (int i = 0; i < M; i++) {
    int u = sc.nextInt();
    int v = sc.nextInt();
    adj[u].add(v);
    adj[v].add(u); // 양방향 그래프이므로 서로 연결
}

for (int i = 1; i <= N; i++) {
    Collections.sort(adj[i]); // 작은 번호부터 탐색하도록 정렬
}

---

🔧 알고리즘 작성

import java.util.*;

public class Main {
    static int N, M, V;
    static List<Integer>[] adj;
    static boolean[] vis;

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

        N = sc.nextInt();
        M = sc.nextInt();
        V = sc.nextInt();

        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj[u].add(v);
            adj[v].add(u);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(adj[i]);
        }

        vis = new boolean[N + 1];
        DFS(V);
        System.out.println();

        vis = new boolean[N + 1];
        BFS(V);
    }

    public static void DFS(int cur) {
        System.out.print(cur + " ");
        vis[cur] = true;

        for (int nxt : adj[cur]) {
            if (!vis[nxt]) {
                DFS(nxt);
            }
        }
    }

    public static void BFS(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        vis[start] = true;

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

            for (int nxt : adj[cur]) {
                if (!vis[nxt]) {
                    vis[nxt] = true;
                    q.add(nxt);
                }
            }
        }
    }
}

해당 코드를 통해 사용자의 입력을 받고, 노드와 간선을 연결한 후 각 탐색을 수행하여 결과를 출력하였다.

DFS와 BFS 코드는 C 외에 언어로 처음 작성해보기에 외부 링크에서 알고리즘을 가져다가 활용하였다.

---

참고 자료

https://velog.io/@suk13574/알고리즘Java-BFS-DFS
https://binco.tistory.com/entry/Java-알고리즘-DFS와BFS-완벽정리
https://www.acmicpc.net/board/view/152080