백준 #1260) DFS와 BFS 자바

분석하다

---

이 문제를 해결하려면 먼저 bfs와 dfs에 대해 알아야 합니다.

dfs와 bfs는 그래프 검색에 사용되는 알고리즘이지만 구현 방식이 다르기 때문에 목적에 따라 다른 알고리즘을 사용한다.

(*그래프: 노드와 에지로 구성된 데이터 구조의 일종)

깊이 우선 탐색(bfs)

루트 노드에서 시작하여 다음 분기로 이동하기 전에 해당 분기를 완전히 통과하는 방법입니다.

스택 또는 재귀 함수로 구현할 수 있지만 재귀 함수로 구현하면 코드가 더 간단해집니다.

모든 노드를 방문해야 하거나 그래프가 클 때 사용

너비 우선 검색(bfs)

– 이웃 노드를 먼저 찾는 방식.

가까운 노드를 먼저 방문하고 먼 노드를 나중에 방문합니다.

대기열로 구현할 수 있습니다.

최단 경로를 찾는 데 사용

암호

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int node, line, start;
    static int()() arr;
    static boolean() visit;

    public static void main(String() args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());

        visit = new boolean(node + 1);
        arr = new int(node + 1)(node + 1);

        for (int i = 0; i < line; i++) {
            StringTokenizer str  = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            arr(a)(b) = arr(b)(a) = 1;
        }


        dfs(start);
        visit = new boolean(node + 1);
        sb.append("\n");
        bfs(start);
        System.out.println(sb);
    }

    static void dfs(int start) {
        sb.append(start + " ");
        visit(start) = true;
        for (int i = 1; i <= node; i++) {
            if (arr(start)(i) == 1 && !
visit(i)) {
                dfs(i);
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();

        q.add(start);
        visit(start) = true;

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

            for(int i=1;i<=node;i++){
                if(arr(value)(i) == 1 && !
visit(i)){
                    visit(i) = true;
                    q.add(i);
                }
            }

        }
    }


}