[백준] 1260 DFS와 BFS | 그래프, DFS, BFS | 실버 Ⅱ | JAVA 💡뼈대 문제

📌 문제

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

 

⭐ 정답코드

import java.io.*;
import java.util.*;

public class Main{  
  static boolean[][] a;
  static boolean[] visited;

  static StringBuilder sb = new StringBuilder();

  static int n;

  static Queue<Integer> q = new LinkedList<>();
  
  public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());

    n = Integer.parseInt(st.nextToken());
    int e = Integer.parseInt(st.nextToken());
    int start = Integer.parseInt(st.nextToken());

    a = new boolean[n+1][n+1];
    visited = new boolean[n+1];

    for (int i = 0; i<e; i++){
      st = new StringTokenizer(br.readLine());
      int node1 = Integer.parseInt(st.nextToken());
      int node2 = Integer.parseInt(st.nextToken());
      a[node1][node2] = true;
      a[node2][node1] = true;
    }

    dfs(start);
    sb.append("\n");

    visited = new boolean[n+1];

    bfs(start);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }

  public static void dfs(int start){
    sb.append(start+" ");
    visited[start] = true;

    for (int i = 1; i<=n; i++){
      if (!visited[i] && a[start][i]) {
        dfs(i);
      }
    }
  }

  public static void bfs(int start){
    q.add(start);
    visited[start] = true;

    while (!q.isEmpty()){
      start = q.poll();
      sb.append(start+" ");

      for (int i = 1; i<=n; i++){
        if (!visited[i] && a[start][i]){
          q.add(i);
          visited[i] = true;
        }
      }
    }
  }
}

 

✅ 그래프 구성

그래프는 인접 행렬(boolean[][] a)을 사용하여 표현됩니다. 이 행렬에서 a[i][j]가 true이면 정점 i와 정점 j가 연결되어 있음을 의미합니다. 방문 여부는 visited[] 배열로 관리합니다.

 

✅ DFS 

DFS는 후입선출 방식으로 작동합니다.

즉, 가장 최근에 방문한 정점을 먼저 탐색합니다.

구현 방식은 재귀 호출을 사용하여 깊이 깊이 탐색해 나갑니다.

⏹️ 과정

1. 시작 정점 방문:
   • dfs(start) 함수가 호출되면 현재 정점을 방문하고, 방문한 정점을 결과에 추가합니다.
   • 예를 들어, 시작 정점이 1이라면 결과는 1이 됩니다.
2. 이웃 정점 탐색:
   • 현재 정점의 모든 이웃을 확인합니다.
   • 이웃 정점 중에서 아직 방문하지 않은 정점이 있다면, 그 정점으로 재귀 호출을 합니다.
3. 재귀 호출:
   • 예를 들어, 1의 이웃 정점이 2, 3, 4라면, DFS는 가장 작은 정점인 2로 이동합니다.
   • 이제 dfs(2)를 호출하게 되고, 방문 상태로 표시한 후 결과에 2를 추가합니다.
4. 탐색 깊이:
   • 현재 정점 2에서 또 이웃을 탐색합니다. 예를 들어, 2의 이웃이 3, 4라고 가정하면 DFS는 다음으로 3으로 이동합니다.
   • 이 과정이 반복되어, 더 이상 갈 수 없는 정점에 도달하면, 호출 스택이 되돌아가면서 이전 정점으로 돌아옵니다.
5. 되돌아가기:
   • DFS는 재귀적으로 깊이 들어간 후에 더 이상 갈 곳이 없으면 호출 스택을 따라 올라가면서, 그 경로를 되돌아가게 됩니다.
   • 이로 인해 DFS는 가장 깊은 정점부터 탐색을 종료하게 됩니다.

 

✅ BFS

BFS는 선입선출 방식으로 작동합니다.

즉, 먼저 큐에 들어간 정점이 먼저 탐색됩니다.

큐를 사용하여 현재 정점의 이웃을 탐색하고, 이웃들을 모두 큐에 추가한 후 하나씩 꺼내어 탐색합니다.

⏹️ 과정

1. 시작 정점 추가:
   • bfs(start) 함수를 호출하면 시작 정점을 큐에 추가합니다.
   • 예를 들어, 시작 정점이 1이라면 큐에는 [1]이 됩니다.
   • 이때, 정점 1은 방문 상태로 표시됩니다.
2. 큐에서 정점 꺼내기:
   • 큐에서 정점을 하나 꺼내는 작업은 가장 먼저 들어간 정점부터 꺼내는 방식입니다.
   • 위의 예에서 큐에서 1을 꺼내면, 이제 큐는 비어있습니다: [].
3. 이웃 정점 추가:
   • 꺼낸 정점(여기서는 1)의 이웃을 확인하고, 아직 방문하지 않은 정점들을 큐에 추가합니다.
   • 만약 1과 연결된 정점이 2, 3, 4라면, 이 정점들을 큐에 추가합니다. 이제 큐는 [2, 3, 4]가 됩니다.
   • 여기서 방문한 정점 2, 3, 4도 표시해줍니다.
4. 반복:
   • 큐가 빌 때까지 이 과정을 반복합니다. 큐의 첫 번째 정점을 계속 꺼내어, 그 정점의 이웃을 큐에 추가하는 방식입니다.
   • 큐에서 꺼내는 순서는 다음과 같습니다:
     1. 2 꺼내기: 큐는 [3, 4]가 되고, 2의 이웃 정점(예를 들어 5, 6)을 큐에 추가하면 [3, 4, 5, 6]이 됩니다.
     2. 3 꺼내기: 큐는 [4, 5, 6]가 되고, 3의 이웃 정점(예를 들어 7)을 큐에 추가하면 [4, 5, 6, 7]이 됩니다.
     3. 4 꺼내기: 큐는 [5, 6, 7]가 되고, 4의 이웃을 추가합니다.

 

 🚩 결론

DFS는 후입선출 방식으로 깊이 탐색하고, BFS는 선입선출 방식으로 너비 탐색을 합니다.

이 차이로 인해 각각의 탐색 방식이 그래프에서 다르게 동작하며, 방문하는 정점의 순서도 달라지게 됩니다.

DFS는 주로 경로를 찾거나 트리 구조를 깊이 탐색할 때 유용하고, BFS는 최단 경로를 찾거나 넓은 범위의 탐색이 필요할 때 효과적입니다.