DFS (Depth-First Search) 알고리즘 정리

오늘은 알고리즘에서 가장 중요한 개념중에 하나인 DFS에 대해 설명을 드리고자 한다.

 

DFS는 다양한 경우의 수를 구할때 굉장히 많이 쓰이는 알고리즘이나 꼭 익혀두길 권장한다.

 

일단 코드소스를 먼저 보여드리겠다.

 

public class DFS {
	public static void main(String args[]) {
		DFS tree = new DFS();
		Node root = new Node(1);
		root.lt = new Node(2);
		root.rt = new Node(3);
		root.lt.lt =new Node(4);
		root.lt.rt = new Node(5);
		root.rt.lt = new Node(6);
		root.rt.rt = new Node(7);
		tree.dfs(root);
	}

	public void dfs(Node root) {
		if(root == null) return;
		else {
			//System.out.println(root.data); 전위 순회
			dfs(root.lt);
			//System.out.println(root.data); 중위 순회
			dfs(root.rt);
			//System.out.println(root.data); 후위 순회
		}
	}
}

class Node {
	int data;
	Node lt;
	Node rt;

	public Node(int data) {
		this.data = data;
		this.lt = null;
		this.rt = null;
	}
}

 

여기서 dfs 함수 내부를 보면 아시겠지만 재귀함수가 사용되는것을 볼 수 있다. 재귀함수에 대해 잘 모르시는 분이라면 아래글을 참고하자.

https://devkingdom.tistory.com/262

재귀 함수 정리

 

public static void main(String args[]) {
		DFS tree = new DFS();
		Node root = new Node(1);
		root.lt = new Node(2);
		root.rt = new Node(3);
		root.lt.lt =new Node(4);
		root.lt.rt = new Node(5);
		root.rt.lt = new Node(6);
		root.rt.rt = new Node(7);
		tree.dfs(root);
	}

다시 코드로 가서 메인에 내가 입력한 코드는 트리를 만드는 것인데 여기서 tree를 만든것을 표현하면 아래의 그림과 같이 보일 것이다. 

여기서 main 의 맨 아랫줄에 호출한 dfs함수가 호출되게 되면 이제 탐색을 시작한다.

 

오늘은 전위, 중위, 후위 순회 중에 전위만 스택프레임이 쌓여서 처리되는 것을 확인해볼까한다. 나는 흘러가는 구조를 익히기 위해 직접 다그려보았다... 여러분들도 한번 쭉 그려보면 좋을 것 같다.

 

링크로 첨부한 재귀함수 호출 방법을 안다면ㄴ 위의 그림처럼 스택 프레임이 왜 저렇게 동작하는지를 알 수 있을꺼다. 다시 한번 말씀드리지만 ... 꼬옥 그려보길 권장드린다.

 

끝.