자바 알고리즘 - 이진트리 순회, DFS

오늘은 DFS 깊이 우선 탐색에 대해서 공부하였다. 새로운 것 두 가지를 알았는데

- DFS 는 생각보다도 훨~~씬 어렵고 심오하다는 것과

- 바로 이 DFS 로 조합과 관련된 문제를 풀 수 있다는 것

이다.

 

사실 지금까지는 조합과 관련된 문제를 풀어보려고 몇 번 뒤적뒤적 했던 적이 있다. 그럴때마다 문제도 이해가 안되었지만, 대체 이걸 코드로 어떻게 짜는거지? 라고 생각될 때가 많았다. 그렇다, 문제가 어려웠던 것은 그렇다치고, 조합에 관한 부분을 대체 어떻게 짜는거지? 하면서 뭔가 풀이 방법조차 떠오르지 않았던 것은 바로 이 DFS , BFS 에 대해서 공부하지 않았기 때문이었다.

 

앞으로 적을 DFS 와 BFS 의 개념은 엄청 엄청!!! 아주아주 매우매우 중요하다. 이걸 쓰는 코딩 테스트 문제들은 물론이요 조금 난이도가 있따 싶으면 다 이런 개념들이 들어가지 않나 생각된다. 

신비하고 오묘한 코딩의 세계, 공부할수록 할게 많아지고, 공부할수록 신기한게 튀어나온다ㅋㅋㅋ

 

1. 트리 순회

※ 여기서 나오는 부모노드 자식노드에 대한 부분은 대충이라도 알고 있다고 가정하에 넘어가겠습니다. 그것까지하면 너무 오래걸려서ㅠㅠ

• 이진트리는 대충 아래처럼 생긴 tree 모양

2. 트리 순회는 방법 총 3가지 방법이 있다. 기준은 부모 노드를 기준으로 전위, 중위 후위로 나뉜다.

• 전위 순회 : 부모 - 왼쪽 - 오른쪽
  • 1 - 2 - 4 - 5 - 3 - 6 - 7
• 중위 순회 : 왼쪽 - 부모 - 오른쪽
  • 4 - 2 - 5 - 1 - 6 - 3 - 7
• 후위 순회 : 왼쪽 - 오른쪽 - 부모
  • 4 - 5 - 2 - 6 - 7 - 3 - 1

위 그림을 보다 이해하기 쉬운 코드로서의 트리로 그림을 그리면 아래와 같다. data 는 Node 라고 생각하면 되고, 뒤에 나오는 100, 200 , 300 등은 임의로 붙여둔 주소값으로 생각하면 된다. lt 는 left tree, rt 는 right tree 로 각각 왼쪽 자식노드 오른쪽 자식 노드를 의미한다.

• data = 1 일 때(Node = 1) 는 100 의 주소값을 갖고, 왼쪽 자식 노드(lt) 는 data = 2, 200 을 갖으며, 오른쪽 자식 노드(rt) 는 data = 3, 300 을 갖는다.
• Node 4 와 5 의 자식노드가 없음으로 각각의 lt, rt 모두 null 값을 갖는다(비어있으면 null 로 표시).
• 전위 순회 : 1 - 2 - 4 - 5 - 3 - 6 - 7

 

2. DFS - 전위 순회

• 이제 이 트리 구조를 갖고 전위 순회를 DFS 방식의 코드로 구현하도록 하겠다.
• DFS 에서 재미있는 점은 재귀 구조를 갖는다는 점이다. 자기 자신을 호출함으로써 값을 계산하고 return 한다는 것.
• 이거는 코드 안에 열심히! 설명을 적어두었으니 그것을 참고해주시면 감사하겠습니다.
• print 부분을 앞에 두면 전위 순회, DFS(lt) DFS(rt)중간에 두면 중위 순회, 맨 위에 두면 후위 순회를 출력 할 수 있다.

package Algorithm;

import java.util.*;

public class Algo_3 {
	Node root;
	
	public void DFS(Node root) {
		if(root == null) { // 말단 노드는 값이 없음(null), 즉 말단 노드에 도착했을 때 종료
			return;
		}else {
			System.out.print(root.data+ " -> "); // 전위 순회
			DFS(root.lt); // 트리에서 왼쪽으로 값을 전달
//			System.out.print(root.data+ " -> "); // 중위 순회
			DFS(root.rt); // 트리에서 오른쪽으로 값을 전달
//			System.out.print(root.data+ " -> "); // 후위 순회

		}
	}
	
	public static void main(String args[]) {
		// 구체적인 부분은 위쪽 그림 참고하면서 볼 것
		
		Algo_3 tree = new Algo_3();
		tree.root = new Node(1);  
		tree.root.lt = new Node(2);  
		tree.root.rt = new Node(3);	
		// root.data = 1, root.lt = 2 , root.rt = 3 값을 갖는다.
		// 그림 상에서는 첫 번째 root 노트에 해당하며 보다 쉽게 root.data 가 1 일 때 100의 주소값을 갖는다고 생각하면 좋다
		// 이렇게하면 root.data = 2 일 때는 주소값 200, root.data = 3 일때는 주소값 300 이 된다. 
		
		tree.root.lt.lt = new Node(4);
		tree.root.lt.rt = new Node(5);
		// root.data = 4 일때 주소값은 400 이다. 그러나 이후 연결되는 자식 노드가 없기 때문에 각 lt , rt 값은 null 을 갖는다.
		// 마찬가지로 root.data = 5 일때도 자식 노드가 없음으로 lt , rt 값은 null 이 들어간다. 
		
		tree.root.rt.lt = new Node(6);
		tree.root.rt.rt = new Node(7);
		
		tree.DFS(tree.root);
		
	}
}

class Node{
	int data;
	Node lt, rt; // Node 의 객체 주소를 저장하는 변수, 2개가 나오는 이유는 노드가 뻗을 때 한곳으로만 뻗는게 아니라 2곳으로 뻗어나가기 때문에
	
	public Node(int val) {
		data = val; // data 에는 val 값을 넣기
		lt=rt=null; // lt 와 rt 가 생성될 때 기본값은 null 즉 데이터가 들어가지 않을때는 null
	}
}

전위 순회 출력 완료!

 

3. DFS 로 부분집합 구하기!

• 앞서 살짝 언급했지만 DFS 는 조합 문제에 특히 사용할만 하다고 생각한다.
• 대표적으로는 부분집합이 몇개인지 구하는 문제가 있는데 이 문제도 일종의 조합 문제이다. 즉, 각각의 원소로 만들 수 있는 집합의 갯수를 구하는 것이기 때문이다.
  
  • 부분집합을 구하는 공식은 2^n 이다. 이때 n 은 원소의 갯수!

• 문제 : 원소 1 2 3 을 갖는 집합 하나가 존재한다. 이때 부분집합의 갯수는 몇 개 일까?, 단 공집합은 계산하지 않는다. => 집합 : {1, 2, 3}, 부분집합 갯수 : 2^3 - 1(공집합 1개) = 7
• 위와 같은 문제를 트리 형식으로 만들어보면 아래 처럼 그림그려질 것이다.
  • 그림은 원소 1 을 기준으로 각 원소의 사용 유무에 따라서 왼쪽(lt) 와 오른쪽(rt) 방향으로 간다.
  • 최종적으로 D(4) 부분, 즉 L = 4 일 때 부분집합이 출력되는데 이는 D(3)에서 해당 원소인 3을 사용하는지 안한는지에 따라서 다시 2가지의 경우로 나뉠 수 있기 때문이라고 생각하면 편하다. 
  • 사실 D(3) 이후에 오는 D(4) 가 null 이기 때문에 해당 Node의 값이 null 일 때 그전까지 축적되었던 값을 출력한다고 생각하면 되지 않을까...?

그림 그리기 힘들어여ㅠ

코드로 풀어보자면 이렇게 된다!!

• 이때 중요한 점은 ch 배열은 일종의 해당 원소를 사용하는지 여부를 확인하기 위한 체크 배열이다. 원소 1과 2는 사용하고 3은 사용하지 않는 경우 해당 배열은 ch = { 1, 1, 0 } 이 될 것이다.
• 또한 출력은 인덱스 번호인 i 를 출력하기 때문에 1과 2만 출력된다.

public class Algo_4_DFS {
	public static void main(String[] args) {
		DFS t = new DFS();
		t.n = 5;
		t.ch = new int[t.n+1];
		t.DFS(1);
		System.out.println("result = "+t.result); // 총 몇개인지 출력
	}
}

class DFS{
	static int n; // 집합 원소 갯수
	static int[] ch; // 체크 배열, 부분 집합으로 사용 여부, 배열의 값이 1 이면 사용O, 0 이면 사용X
	static int result = 0; // 원소가 n 개인 집합의 부분집합 갯수는 2^n
	
	public void DFS(int L) { 
		if(L==n+1) {
			String tmp = ""; 
			
			for(int i=1; i<=n; i++) { // 이때 i 는 인덱스 번호 : 1 2 3
				if(ch[i] == 1) {
					tmp+=(i+" "); // int형 + " " => 문자열 String
				}
			}
			if(tmp.length()>0) { 
            // 공집합인 경우 갖고 있는 값이 없기 때문에 길이는 0 이된다.
            // 즉 공집합이 아닌 경우 출력
				System.out.println(tmp);
				result+=1; // 총 몇개가 나오는지 갯수 확인하기 위해 부분집합 출력때마다 result+1
			}

			return;
		}else {
			ch[L]=1; // L이 부분집합으로 사용되는 경우
			DFS(L+1); // L 에 대한 왼쪽 트리
			
			ch[L]=0; // L이 부분집합으로 사용되지 않는 경우
			DFS(L+1); // L 에 대한 오른쪽 트리
		}
	}
}

요렇게 출력된다

 

 

사실 강의를 들으면서도 이게 대체 뭔 소리냐...를 연달아 외치면서 정리했다. 아마 개념 공부도 열심히하고 문제도 더 많이 풀어봐야겠지 싶다.