[DFS,BFS] 백준 1260번 DFS와 BFS

DFS(깊이우선 탐색)

최대한 깊이 내려간후 더이상 내려갈 노드가 엎다면 옆으로 이동하여 탐색하는방법

구현방법: 스택 또는 재귀함수

유리한 문제: 경로의 특징을 저장하는 문제

 

BFS(너비우선 탐색)

루트노드로 부터 가까운 노드 부터 탐색하는 방법

구현방법: 큐

유리 한문제: 최단거리

 

package BaekJoon.DFS_BFS;
import java.io.*;
import java.util.*;

public class No1260 {
    static boolean[] checked = new boolean[1001]; //탐색여부
    static int N; //정점
    static int M; //간선
    static int V; //시작정점

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        V = sc.nextInt();

        int[][] check = new int[1001][1001];

        //간선 입력
        for(int i = 0; i < M; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            check[x][y] = check[y][x] = 1;
        }

        dfs(V, check);
        checked = new boolean[1001]; //탐색여부 초기화

        System.out.println();

        bfs(V, check);
    }


    public static void dfs(int v, int[][] check) {
        checked[v] = true;
        System.out.print(v + " ");

        for(int j = 1; j <= N; j++) {
            if(check[v][j] == 1 && checked[j] == false) {  //탐색한적 없는 간선이 있는지 확인
                dfs(j, check);     //재귀를 통해 아래 노드로 이동
            }
        }
    }

    public static void bfs(int v, int[][] check) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(v); //시작점 큐에 삽입
        checked[v] = true;
        System.out.print(v + " ");

        while(!q.isEmpty()) {
            int temp = q.poll();

            for(int j = 1; j <= N; j++) {
                if(check[temp][j] == 1 && checked[j] == false) {
                    q.offer(j);
                    checked[j] = true;
                    System.out.print(j + " ");
                }
            }
        }
    }
}