DFS 알고리즘 공부하기

Deep First Search
https://youtu.be/PMMc4VsIacU

그래프 탐색 알고리즘 중 1


각 노드(?)들을 vertex라고 부름

recursive

파라미터로 그래프와 visit할 vertex를 넣음
그 vertex의 이웃들을 loop돌려서 탐색.
이웃들의 이웃들도 탐색하기 위해 재귀로 dts또 호출

이미 visit한 vertex에 다시 돌아가지 않기위해 mark해주는 로직 추가함.

iterative

key differece - use stack data structure to keep track nodes to visit

재귀를 쓰는대신 stack에 v의 이웃노드들을 넣어서 체크

Preorder & Postorder

preorder - 다음 vertext로 갈때 output
postorder - 더이상 이웃이 없을때 output

여기서 visit은 출력. output

백준으로연습

DFS 연습문제 찾다가 백준 미로찾기 풀기 시도했는데 알고보니 그건 BFS로 풀어야한다고함;; 삽질 오지게했네
그래도 좀 익숙해진듯.
암튼 그래서 그거대신 DFS와 BFS라는 문제중에 DFS부분만 품.
오늘은 도저히 BFS까지 공부할수없음. 다른거 할것도 많음.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;



public class DfsBfs {
    static int[][] arr;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        //int N = 정점 수
        //int M = 간선수
        //int V = 시작할 노드
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        int V = Integer.parseInt(str[2]);
        visited=new boolean[N+1];

        //인접행렬
        arr = new int[N+1][N+1];
        for(int i=0;i<M;i++){
            String[] nums = br.readLine().split(" ");
            int x = Integer.parseInt(nums[0]);
            int y = Integer.parseInt(nums[1]);
            arr[x][y]=1;
        }

        dfs(V);

    }

    private static void dfs(int v) {
        System.out.println(v);

        if(v == arr.length){
            return;
        }
        visited[v]=true;
        for(int i = 1;i<arr.length;i++){
            if(arr[v][i]==1 && !visited[i]){
                dfs(i);
            }

        }
    }

}

어휴.. 인터넷 참고해서 겨우풀었네
응용은 역시 어렵다
이번 한주동안 dfs에 익숙해지게 dfs문제좀 풀어야겠음. 그리고 bfs도 공부해야겠음