DFS와 BFS

깊이 우선 탐색 (DFS, Depth-First Search)
: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

스택 또는 재귀함수로 구현

너비 우선 탐색 (BFS, Breadth-First Search)
: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

큐를 이용해서 구현

💻 코드

DFS와 BFS을 사용한 JAVA코드

import java.util.*;

public class DFSBFS
{
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    public static void dfs(int x)
    {
        visited[x] = true;
        System.out.println(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for(int i = 0; i < graph.get(x).size(); i++)
        {
            int y = graph.get(x).get(i);
            if(!visited[y]) dfs(y);
        }
    }

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

        while(!q.isEmpty())
        {
            int x = q.poll();
            System.out.println(x + " ");

            for(int i = 0; i < graph.get(x).size(); i++)
            {
                int y = graph.get(x).get(i);
                if(!visited[y])
                {
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }
}

📌참고

출처: https://devuna.tistory.com/32 [튜나 개발일기]