[JAVA][Baekjoon] 1260번 DFS와 BFS 🌟

https://www.acmicpc.net/problem/1260

---

📌 접근 방식

1️⃣ DFS(Depth First Search):

• 깊이 우선 탐색
  ➡️한 노드에서 가능한 멀리까지 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방법 
• 스택 또는 재귀 호출을 활용해 구현 (이번엔 재귀 방식으로 구현!)

2️⃣ BFS(Breadth First Search):

• 너비 우선 탐색
  ➡️ 한 노드의 인접 노드들을 모두 탐색한 후, 그다음 깊이를 탐색
• 큐(Queue)를 사용해 구현

[알고리즘] 깊이 우선 탐색 : DFS(Depth-First-Search)

 

[알고리즘] 너비 우선 탐색 : BFS(Breadth-First-Search)

---

✅ PASS CODE

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        A = new ArrayList[N+1];
        for(int i=1; i<=N; i++) {
            A[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
        }
        for(int i=1; i<=N; i++) {
            Collections.sort(A[i]);
        }
        visited = new boolean[N+1];
        DFS(V);
        System.out.println();
        visited = new boolean[N+1];
        BFS(V);
        System.out.println();
    }
    public static void DFS(int start) {
        System.out.print(start + " ");
        visited[start] = true;
        for(int i : A[start]) {
            if(!visited[i]) {
                visited[i] = true;
                DFS(i);
            }
        }
    }
    public static void BFS(int start) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start);
        visited[start] = true;

        while(!queue.isEmpty()) {
            int cur = queue.poll();
            System.out.print(cur + " ");
            for(int i : A[cur]) {
                if(!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

💡 코드 분석

1️⃣ DFS 구현

DFS는 재귀 호출로 구현되며, 방문한 노드는 바로 출력

public static void DFS(int start) {
    System.out.print(start + " ");
    visited[start] = true; // 방문 처리
    for (int i : A[start]) { // 인접 노드 순회
        if (!visited[i]) {
            visited[i] = true; // 방문 체크
            DFS(i); // 재귀 호출
        }
    }
}

 

2️⃣ BFS 구현

BFS는 큐를 활용하여 방문 노드를 관리

public static void BFS(int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start); // 시작 노드 삽입
    visited[start] = true; // 방문 처리

    while (!queue.isEmpty()) { // 큐가 빌 때까지
        int cur = queue.poll(); // 큐에서 꺼내기
        System.out.print(cur + " ");
        for (int i : A[cur]) { // 인접 노드 순회
            if (!visited[i]) {
                visited[i] = true; // 방문 체크
                queue.add(i); // 큐에 삽입
            }
        }
    }
}

3️⃣ 입력 및 초기화

그래프 크기, 간선, 시작 정점 번호를 입력받고 초기화

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());

간선 정보를 읽어 그래프를 구성한 뒤, 방문 배열을 초기화함

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

---

반응형

🧐 느낀점

이번 문제를 통해 DFS와 BFS의 개념과 특성을 더 명확히 이해할 수 있었다! 🔍

두 탐색 방법의 차이와 적용 방식을 완전히 이해하게 되었고, 이를 바탕으로 다양한 그래프 문제를 해결할 수 있을 것 같다. 앞으로 더 복잡한 그래프 문제를 해결할 때도 알고리즘 선택과 효율성에 신경 쓰면서 코드를 개선해 나가야겠다! 💪😊