[알고리즘] DFS - 재귀호출, 스택(Stack)

1. 재귀호출 사용

import java.util.*;

public class Main {
	static final int Max_N = 10;
    static int N, E;
    static int[][] Graph = new int [Max_N][Max_N]; // 노드,간선 정보를 이중배열에 담아둠
    static boolean[] Visited = new boolean[Max_N]; // 노드 방문 여부를 확인하기위함
    
    public static void main(String[] args){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        bfs(0); // 시작노드 0
    }
    
    static void dfs(int node){
    	Visited[node] = true; // 방문한 노드는 true
        System.out.print(node+" ");
        
        for(int next=0; next<N; next++){
        	if(!Visited[next] && Graph[node][next]!=0){ // 다음노드가 방문하지 않았던 노드이고, 현재노드-다음노드 사이에 간선이 존재한다면
            	dfs(next); 
            }
        }
    }
}

 

 

 

 

 

2. 스택 사용

import java.util.*;

public class Main {
	static final int Max_N = 10;
    static int N, E;
    static int[][] Graph = new int [Max_N][Max_N]; // 노드,간선 정보를 이중배열에 담아둠
    
    public static void main(String[] args){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        bfs(0); // 시작노드 0
    }
    
    static void dfs(int node){
    	boolean[] Visited = new boolean[Max_N]; // 노드 방문 여부를 확인하기위함, 재귀호출이 아니므로 static 선언 안해도 StackOverFlow 발생하지않음
    	
        Stack<Integer> myStack = new Stack<>;
        myStack.push(node);
        
        while(!myStack.empty()){
        	int curr = myStack.pop();
            
            if(Visited[curr]) continue;
            
            Visited[curr] = true;
            System.out.print(curr + " ");
            
            for(int next=0; next<N; next++){
        	if(!Visited[next] && Graph[node][next]!=0){ // 다음노드가 방문하지 않았던 노드이고, 현재노드-다음노드 사이에 간선이 존재한다면
            	myStack.push(next);
            }
        }

    }
}

 

 

핵심 => 결과에 상관없이 모두 깊이우선탐색이다.

 

 

 

 

 

 

 

 

출처 : https://www.youtube.com/watch?v=0Njv04WiLV0