[탐색] 깊이 우선 탐색(DFS)

💡 먼저 부족하지만 저의 글을 읽어주셔서 감사드립니다!!!
참고 정도로 해주셨으면 좋겠습니다.
해당 강의는 여기 사이트 입니다.

 

깊이 우선 탐색(Depth-First Search)

• 하나의 노드에서 시작해 마지막 지점까지 계속 그래프를 탐색
• 미로찾기, 당신을 알 수 있는 친구 찾기 등

 

내가 강의를 들으면서 생각한 중요한 부분은

 

1. 노드(node)라고 불리는 각 지점들과 지점들을 연결하는 간선(edge) 이다.
2. 인접행렬의 1과 0 즉, 연결이 되어있으면 1 아니면 0을 이해하면 된다.!

 

이미지에서와 같이 0부터시작하여 1번 → 3번 → 4번 → 2번 순서대로 간다.

 

여기서 어떻게 우리는 1번에서 3번 4번으로 갈 수 있을까 생각하는데 코드를 한 번 봤으면 좋겠다.

 

if (!visited[next] && Graph[curr][next] != 0) {
    mystack.push(next);
}

 

조건문에서 첫 번째 조건 방문의 여부와 간선(line)이 있는지 여부의 두 번째 조건으로 판단할 수 있다.

 

 

 

👉 재귀호출

public class App {

    static final int MAX_N = 10;
    static int vertex, line; // 각각의 노드와 간선
    static int[][] Graph = new int[MAX_N][MAX_N];   // 인접행렬 0과 1
    
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        vertex = sc.nextInt();
        line = sc.nextInt();

        for (int i = 0; i < line; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            Graph[u][v] = Graph[v][u] = 1;
        }
        dfs(0);
    }

    public static void dfs(int node) {
        boolean[] visited = new boolean[MAX_N];

        Stack<Integer> mystack = new Stack<>();
        mystack.push(vertex);

        while (!mystack.empty()) {
            int curr = mystack.pop();

            if (visited[curr]) continue;

            visited[curr] = true;
            System.out.println(curr + " ");

            for (int next = 0; vertex < next; next++) {
                if (!visited[next] && Graph[curr][next] != 0) {
                    mystack.push(next);
                }
            }
    	}
    }
}

 

 

👉 Stack

public class App {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        vertex = sc.nextInt();
        line = sc.nextInt();

        for (int i = 0; i < line; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            Graph[u][v] = Graph[v][u] = 1;
        }
        dfs(0);
    }


    public static void dfs(int node) {
        boolean[] visited = new boolean[MAX_N];

        Stack<Integer> mystack = new Stack<>();
        mystack.push(vertex);

        while (!mystack.empty()) {
            int curr = mystack.pop();

            if (visited[curr]) continue;

            visited[curr] = true;
            System.out.println(curr + " ");

            for (int next = 0; vertex < next; next++) {
                if (!visited[next] && Graph[curr][next] != 0) {
                    mystack.push(next);
                }
            }
        }
        
    }
}