깊이 우선 탐색 (DFS) & 너비 우선 탐색 (BFS )

❓공부하게 된 계기

➡️ 다음주 알고리즘 스터디 주제인 DFS & BFS 에 대해서 예습

❗️공부한 내용

1️⃣ 관련 자료구조

➡️ DFS 와 BFS 에 대해 공부하기전 알아두어야할 자료구조가 있다.

 

① Stack & Queue

➡️ 해당 내용은 과거 이미 정리했던 내용이라 해당 글을 링크해두는 것으로 마무리한다.

(Java) 스택(Stack) & 큐(Queue)

② 재귀 함수 (Recursive Function)

➡️ 기본적인 개념은 알고 있으니 특이사항 정도만 정리해두면 될 것 같다.

- 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있지만, 다른 사람이 이해하기 어려운 형태가 될 수 있으므로 신중하게 사용해야한다.
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있고, 따라서 문제에 따라 반복문과 재귀함수 중 유리한 형태를 잘 골라야한다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. 이러한 점을 활용해서 스택 사용시 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

2️⃣ DFS (Depth-First Search)

➡️ 그래프에서 깊은 부분은 우선적으로 탐색하는 깊이 우선 탐색 알고리즘이며, 스택 자료구조나 재귀를 활용하여 구현 한다. 

 

① 동작 과정

(1)  탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

(2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

(3) 더 이상 과정 (2) 를 수행할 수 없을 때 까지 반복한다.

 

② 예시

➡️ 시작 노드는 1 이고, 방문하지 않은 인접 노드가 여러개 있을 때 방문 순서는 번호가 낮은 순이라고 하자

➡️ 노란색 배경은 현재 최상위 노드이고, 회색 배경은 방문 처리된 노드이다.

➡️ 특히 6번 노드까지 방문했을 때 더 이상 인접 노드가 없으므로 스택에서 뺴내고 다시 최상단인 7번 노드를 기점으로 인접노드를 탐색하는 과정을 잘 이해할 수 있다면 해당 알고리즘을 잘 이해했다고 볼 수 있을 것이다.

 

③ 구현 코드

public static Main {
    public static boolean[] visited = new boolean[(노드의 개수)];
    // graph 구현을 위해 2차원 리스트 사용 대신 ArrayList 를 중첩하여 사용
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    
    // DFS 함수 정의
    public static void dfs (int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        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 main(String[] args) {
        /*
            그래프 연결 생략
        */
        dfs(1); // 1번 노드부터 시작
    }
}

3️⃣ BFS (추후 정리)

✏️ 적용 시켜본 예제

🧐 추가로 궁금한 점