[BOJ/] 백준 1260 - DFS와 BFS (Java)

1260 - DFS와 BFS

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

문제

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문, 더 이상 방문할 수 있는 점 X -> 종료
정점 번호: 1 ~ N번

입력
첫째 줄에 정점의 개수 N (1 <= N <= 1,000), 간선의 개수 M (1 <= M <= 10,000), 탐색을 시작할 정점의 번호 V
다음 M개의 줄에는 간선이 연결하는 두 정점의 번호 주어짐
어떤 두 정점 사이에 여러 개의 간선이 있을 수 있음/ 입력으로 주어지는 간선은 양방향
출력: V부터 방문된 점을 순서대로 출력
DFS
BFS

---

풀이

DFS

깊게, 한 방향으로 끝까지 파고들다가 돌아옴/ 재귀

static void dfs(int node) {
    System.out.print(node + " ");
    visited[node] = true;

    for (int next : graph[node]) {
        if (!visited[next]) dfs(next);
    }
}

 

BFS

넓게, 가까운 것부터 탐색/ 큐

static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.offer(start);

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

        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

 

예시

정점 수 N = 4, 간선 수 M = 5, 시작 정점 V = 1

• graph[1] = [2, 3, 4]
• graph[2] = [1, 4]
• graph[3] = [1, 4]
• graph[4] = [1, 2, 3]

 

• `dfs(1)` -> 1 출력, 방문 O
  • -> 인접 노드 [2, 3, 4] 중 2 확인
• `dfs(2)` -> 2 출력, 방문 O
  • -> 인접 노드 [1, 4] 중 1 방문 O -> 4 확인
• `dfs(4)` -> 4 출력, 방문 O 
  • -> 인접 노드 [1, 2, 3] 중 1, 2 방문 O -> 3 확인
• `dfs(3)` -> 3 출력, 방문 O
  • -> 인접 노드 [1, 4] 모두 방문 O => 종료

=> 출력: 1 2 4 3

 

• `bfs(1)` -> 방문 O + 큐 삽입
  • 큐 [1] -> `poll()` -> 1 출력
  • 인접 노드 [2, 3, 4] 모두 방문 O + 큐 삽입
• 큐 [2, 3, 4]
  • `poll()` -> 2 출력 -> 인접 노드 [1, 4] 모두 방문 O => 무시
  • `poll()` -> 3 출력 -> 인접 노드 [1, 4] 모두 방문 O => 무시
  • `poll()` -> 4 출력 -> 인접 노드 [1, 2, 3] 모두 방문 O => 무시
  • => 종료

=> 출력: 1 2 3 4

---

코드

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

// DFS와 BFS
public class boj_1260 {
    static int N, M, V;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;

    static void dfs(int node) {
        System.out.print(node + " ");
        visited[node] = true;

        for (int next : graph[node]) {
            if (!visited[next]) dfs(next);
        }
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);

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

            for (int next : graph[cur]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }

    }

    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());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u].add(v);
            graph[v].add(u);
        }

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

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

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