[알감탈] DFS/BFS - <2> 탐색 알고리즘

# DFS (Depth-First Search)

DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 탐색 수행에 O(N)의 시간이 소요된다.

💡DFS 동작 방식 : 스택 자료구조 이용 -> 재귀함수로 구현!

• 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
• 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드(1개)를 스택에 넣고(보통 번호가 낮은 순서부터 넣는다)방문 처리를 한다.
  방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 위 과정을 더 이상 수행할 수 없을 때까지 반복한다.

import java.util.ArrayList;

public class DFSEx {
    // 방문 정보 저장할 리스트
    public static boolean[] visited = new boolean[9];
    // 그래프 저장할 인접 리스트 생성
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 정의
    public static void dfs(int n) {
        // 현재 노드 방문처리
        visited[n] = true;
        System.out.print(n + " ");

        // 현재 노드와 연결된 다른 노드 재귀적으로 방문
        for(int i=0; i<graph.get(n).size(); i++) {
            int next = graph.get(n).get(i);
            if(!visited[next]) dfs(next);
        }
    }
    public static void main(String[] args) {
        // 그래프 노드 초기화
        for(int i=0; i<9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 연결 정보 저장
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
		...

        dfs(1);
    }
}

# BFS (Breadth First Serach)

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가장 가까운 노드부터 탐색하는 알고리즘이다. 탐색 수행에 O(N)의 시간이 소요되며 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.

💡BFS 동작 방식 : 큐 자료구조 이용

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
• 위 과정을 더 이상 수행할 수 없을 때까지 반복한다.

import java.util.*;

public class BFSEx {
    // 방문 정보 저장할 리스트
    public static boolean[] visited = new boolean[9];
    // 그래프 저장할 인접 리스트 생성
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // BFS 함수 정의
    public static void bfs(int n) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(n); // 노드 큐에 집어넣기
        visited[n] = true; // 현재 노드 방문 처리

        while(!q.isEmpty()) {
            int next = q.poll();
            System.out.print(next + " ");
            // 현재 노드와 연결되어 있으면서 방문하지 않은 노드들 큐에 삽입
            for(int i=0; i<graph.get(next).size(); i++) {
                int linked = graph.get(next).get(i);
                if(!visited[linked]) {
                    q.offer(linked);
                    visited[linked] = true;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        // 그래프 노드 초기화
        for(int i=0; i<9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 연결 정보 저장
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
		...

        bfs(1);
    }
    
}