DFS , BFS 이해하기 및 외우기

DFS(깊이 우선 탐색) 최대한 깊이 내려간 후, 더 이상 갈곳 없으면 뒤로 돌아오는 방식
"깊이" 현재 노드에서 연결된 노드를 재귀적으로 따라가는 것 , 미로에서 한길로 가다가 막히면 뒤로 돌아와서 다른 길이 있다면 그 길로 가는 것

 

BFS(너비 우선 탐색) 가까운 노드부터 차례로 탐색하는 방식.
DFS는 스택과 비슷 , BFS는 Queue(FIFO) 방식

 

 

DFS
1. 1번에서 2,3,4로 갈 수 있음 2번 으로 이동
2. 2번에서 1,4 이동할 수 있는데 1은 왔던길이니 4로 이동
3. 4번에서는 3으로 갈 수 있음.
4. 3번에서는 이미 방문했으므로 종료
고로 1->2->4->3

---

BFS
1. graph 리스트에 각 정점의 연결 정보를 저장
2. 시작 정점 1
3. 1에 연결된 정점 : 2,3 -> 오름차순으로 2 먼저 탐색함
4. 2에 연결된 정점 : 4,5 -> 오름차순으로 4 탐색
5. 3에 연결된 정점 : 6

나머지 이미 탐색되어있음 1,2,3,4,5,6

 

bfs는 Queue 인터페이스와 LinkedList를 분리해서 사용 다양한 구현체( LinkedList, PriorityQueue, ArrayDeque 등)을 활용할 수 있음.

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.poll(); // 정상 동작: Queue 인터페이스의 메서드

LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1); // LinkedList 고유의 메서드 사용 가능
list.add(2);
list.removeFirst(); // Queue의 FIFO 원칙과 맞지 않음

큐의 원칙에 위배되지 않게 , 인터페이스를 통해 동작을 방지할 수 있음 
LinkedList<Integer> list = new LinkedList<>();
LinkedList를 인터페이스로 했을경우 종속적이므로 지양

BFS에서 할일을 생각
1. 값 넣어주기
2. 방문 값 true로 바꿔주기
3. queue가 안비었으면 꺼낸 후 출력
4. 현재 노드와 연결된 모드 노드를 확인하고 , 방문하지 않은 노드 방문처리하고 다시 큐에 추가시킴

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.List;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

class Main{
    static int N; // 정점의 개수
    static int M; // 간선의 개수
    static int V; // 정점 시작 번호
    static List<List<Integer>> adjList; // 근접 노드
    static boolean[] visited; // 방문

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        adjList = new ArrayList<>(N+1);
        for(int i=0; i<=N; i++){
            adjList.add(new ArrayList<>());
        }

        for(int i=0; i<M; i++){ // 간선 입력 받아서 넣기
            st = new StringTokenizer(br.readLine()," ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }

        // 각 리스트들 작은 값 먼저 나와야 함
        for(int i=1; i<=N; i++){
            Collections.sort(adjList.get(i));
        }

        visited = new boolean[N+1]; // 방문체크
        dfs(V);
        System.out.println("");// 줄바꿈
        visited = new boolean[N+1]; // 방문체크
        bfs(V);
    }

    // dfs private으로
    public static void dfs(int n){
        visited[n] = true; // 방문했으니
        System.out.print(n + " ");
        for(int neighbor : adjList.get(n)){ // 방문한 노드 연결된 숫자 체크
            if(!visited[neighbor]){
                dfs(neighbor); // 방문 안했으면 다시 넣어서 방문
            }
        }
    }

    // bfs private으로
    public static void bfs(int n){
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        visited[n] = true; // 방문했으니 true

        while(!q.isEmpty()){ // q가 비어있지 않을때 까지
            int current = q.poll(); // 현재 꺼 꺼냄
            System.out.print(current + " ");
            for(int next : adjList.get(current)){
                if(!visited[next]){
                    visited[next] = true;
                    q.add(next); // next 방문 안했으면 다시 넣음
                }
            }
        }
    }
}