BFS,DFS

이동엽·2023년 7월 24일

BFS,DFS 차이

BFS : 넓게 탐색

DFS : 깊게 탐색

DFS 깊이 우선 탐색

특징

재귀,스택 으로 자기 자신을 호출하는 순환 알고리즘 형태이다.
구현할때 반드시 노드를 방문 할때 해당 노드 방문 여부를 검사해야한다. 안하면 무한루프에 빠질수 있다. ex) visit[index] = true;
깊게 가다가 더이상 갈수 없을때 가까운 갈림길로 돌아가서 다시 탐색을 진행하는 방식이다 (미로 탐색 처럼)
모든 노드를 방문 할때에는 이방법을 선택한다.
BFS보다 더 간단하다.
검색속도는 BFS보다 느리다.

// dfs, 재귀, 인접 행렬, i 정점부터 시작한다.
    public static void dfs(int i) {
		visit[i] = true;
		System.out.print(i + " ");
		
		for(int j=1; j<=n; j++) {
			if(map[i][j] == 1 && visit[j] == false) {
				dfs(j);
			}
		}
	}

BFS 너비 우선 탐색

특징

이 알고리즘도 노드 방문 여부를 반드시 해야 무한 루프에 안빠진다.
방문한 노드들을 차례로 저장한 후에 꺼낼수 있는 큐를 사용한다.
시작 정점에서 가까운 정점을 먼저 방문하고 멀리 있는건 나중에 한다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이방법을 사용한다.

// bfs, q사용, 인접행렬, i 정점부터 시작한다.
	public static void bfs(int index) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(i);
		visit[index] = true;
		
		while(!q.isEmpty()) {
			int temp = q.poll();
			System.out.print(temp + " ");
			for(int j=1; j<=n; j++) {
				if(map[temp][j] == 1 && visit[j] == false) {
					q.offer(j);
					visit[j] = true;
				}
			}
		}
	}

예제 문제

1260번: DFS와 BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int map[][];
    static boolean[] visit;
    static int n,m,v;

    static StringBuilder sb = new StringBuilder();
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str," ");
        n = Integer.parseInt(st.nextToken());// 정점 개수
        m = Integer.parseInt(st.nextToken());// 간선 개수
        v = Integer.parseInt(st.nextToken());// 시작 번호
        map = new int[n+1][n+1];
        visit = new boolean[n+1];
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(map[i],0);//Arrays.fill() 배열 값들을 일괄 초기화
        }
        for (int i = 0; i < m; i++) {
            String edge = br.readLine();
            StringTokenizer st1 = new StringTokenizer(edge," ");
            int a = Integer.parseInt(st1.nextToken());
            int b = Integer.parseInt(st1.nextToken());
            map[a][b] = map[b][a] = 1;
        }
        dfs(v);
        sb.append("\n");
        Arrays.fill(visit,false);
        bfs(v);
        System.out.println(sb);
    }

    private static void bfs(int index) {
        q.offer(index);
        visit[index] = true;
        while(!q.isEmpty()){
            int temp = q.poll(); //첫번째 방문한 노드는 빼주기
            sb.append(temp + " ");

            for (int i = 0; i <= n; i++) {
                if(map[temp][i] == 1 && visit[i] == false){
                    q.offer(i);//add는 에러 발생, offer는 false를 리턴함.
                    visit[i] = true;
                }
            }
        }
    }

    private static void dfs(int index) {
        visit[index] = true;
        sb.append(index + " ");
        for (int i = 0; i <= n; i++) {
            if(map[index][i] == 1 &&visit[i] == false){
                dfs(i); //내가 찾은 경로가 만약에 다른 경로가 있으면 바로 다음 곳으로 이동시키고 만약에 없으면, 다시 돌아오는 방식
            }
        }
    }

}