Recursive, Tree, Graph(DFS, BFS 기초) 2 - 이진트리, 부분집합 DFS

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84#

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

 

DFS : 깊이우선탐색

 

 

문제 1 :

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보라

전위순회 출력 : 1 2 4 5 3 6 7

중위순회 출력 : 4 2 5 1 6 3 7

후위순회 출력 : 4 5 2 6 7 3 1

 

풀이 :

이 셋의 기준은 부모이다.

부모를 제일 먼저 방문하는 것은 전위순회이다.

부모를 중간에 방문하면 중위순회이다.

부모를 마지막으로 방문하면 후위순회이다.

전위순회는 부모인 1, 또 부모인 2, 왼쪽자식 4, 뒤로가서 오른쪽자식 5, 뒤로가기, 뒤로가기, 

부모인 3, 왼쪽자식 6, 왼쪽자식 7 순서로 출력한다.

1 2 4 5 3 6 7

 

중위순회는 1을 출력하면 안된다. 부모는 왼쪽 자식이 출력되고 나서 출력되어야 하기 때문이다.

2로 또 들어가서 왼쪽 자식인 4로 들어가서 왼쪽자식 맞으니까 4 출력, 부모인 2 출력, 오른쪽자식 5 출력,

이렇게 왼쪽 서브트리(왼쪽자식들) 다 했으니 1 출력, 3으로 들어가고 6으로 들어가서 6 출력, 3 출력, 7 출력한다.

4 2 5 1 6 3 7

 

후위순회는 1, 2, 4로 들어가서 왼쪽 자식인 4 출력, 그리고 back해서 2로 가는데 출력하면 안된다.

오른쪽 자식인 5로 가서 5를 출력한다. 그리고 다시 뒤로가서 2로 가서 2를 출력한다.

뒤로가서 1로 가는데 역시 출력하면 안된다. 오른쪽 서브트리 다 끝내고 해야한다.

3, 6으로 들어가서 6 출력, 7 출력, 3 출력, 그리고 1을 출력한다.

4 5 2 6 7 3 1

 

 

일단 이진 트리를 생성하는 코드를 작성해보자

소스코드 (이진트리 생성까지만) :

import java.util.*;

class Node {
	int data;
	// 기본형 변수가 값을 저장한다면 클래스형 변수(인스턴스 변수)는 객체의 주소를 저장한다.
	Node lt, rt; 
	public Node(int value) {
		data = value;
		lt = rt = null; // 생성되는 순간 null
	}
}

public class Main {
	Node root; // root는 Node 클래스의 객체 주소를 저장하는 변수 (참조형)
	public void DFS(Node root) {
		// ~~
	}

	public static void main(String[] args) {
    	Main tree = new Main();
        tree.root = new Node(1); // root는 객체 주소, root.data 하면 1이 출력된다.
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.DFS(tree.root);
    }
}

여기까지 이진 트리를 생성하였다. 

다음과 같은 그림과 같이 이진트리가 생성된다.

 

생성된 이진트리

이제 이렇게 생성한 이진트리를 탐색하는 DFS 함수를 작성해보자

 

소스코드 (DFS 함수만 작성) :

// 전위순회
public void DFS(Node root) {
		if (root == null) return;
		else {
			System.out.print(root.data + " ");
			DFS(root.lt);
			DFS(root.rt);
		}
	}

전위순회 : 1 2 4 5 3 6 7 

 

public void DFS(Node root) {
		if (root == null) return;
		else {
			DFS(root.lt);
			System.out.print(root.data + " ");
			DFS(root.rt);
		}
	}

중위순회 : 4 2 5 1 6 3 7

 

생성된 이진트리

이후 그림들은 생략했다..

이런 단계를 거쳐 코드 실행이 이루어진다.

스택 프레임 개념에 대해 알고 있어야 이해할 수 있는 부분이다.

스택 프레임

public void DFS(Node root) {
		if (root == null) return;
		else {
			DFS(root.lt);
			DFS(root.rt);
			System.out.print(root.data + " ");
		}
	}

후위순회 : 4 5 2 6 7 3 1

 

 

 

문제 2 :

자연수 N이 주어지면 1부터 N까지 원소를 갖는 집합의 부분집합을 모두 출력하시오. (공집합 출력 X)

부분집합을 아래의 출력예제와 같은 순서로 출력한다.

 

입력예제

3

출력예제

1 2 3

1 2

1 3

1

2 3

2

3

 

풀이 :

소스코드 :

import java.util.*;
import java.io.*;
class Main {
	static int n; // 집합의 원소 개수
	static int[] ch; // 체크 배열 ( 해당 원소 사용 o , x 체크 )
	public void DFS(int value) {
		if (value == n+1) {
			String tmp = "";
			for(int i=1; i<=n; i++) {
				if(ch[i] == 1) tmp += (i+" ");
			}
			if(tmp.length() > 0) System.out.println(tmp);
		}
		else {
			ch[value] = 1; // 해당 원소를 사용
			DFS(value + 1);
			ch[value] = 0;
			DFS(value + 1);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		ch = new int[n+1]; // 인덱스 번호를 원소로 할 것이기 때문 
		T.DFS(1);
	}
}