Java 코딩테스트 공부/Java 알고리즘 공부

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

2022. 11. 12. 11:52

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) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성

www.inflearn.com

 

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);
	}
}

 

 

'Java 코딩테스트 공부 > Java 알고리즘 공부' 카테고리의 다른 글

Recursive, Tree, Graph 4 - Tree 말단노드까지 가장 짧은 경로 DFS, BFS  (0) 2023.03.19
Recursive, Tree, Graph(DFS, BFS 기초) 3 - 이진트리, 상태트리 BFS  (0) 2023.03.15
Recursive, Tree, Graph(DFS, BFS 기초) 1 - 재귀  (0) 2022.11.09
Java 정렬, 이분검색과 결정알고리즘 3  (0) 2022.11.04
Java 정렬, 이분검색과 결정알고리즘 2  (0) 2022.09.03
'Java 코딩테스트 공부/Java 알고리즘 공부' 카테고리의 다른 글
  • Recursive, Tree, Graph 4 - Tree 말단노드까지 가장 짧은 경로 DFS, BFS
  • Recursive, Tree, Graph(DFS, BFS 기초) 3 - 이진트리, 상태트리 BFS
  • Recursive, Tree, Graph(DFS, BFS 기초) 1 - 재귀
  • Java 정렬, 이분검색과 결정알고리즘 3
daramG
daramG
dotori Java
daramG
다람쥐의 개발 블로그
daramG
전체
오늘
어제
  • 분류 전체보기 (193)
    • Java 코딩테스트 공부 (67)
      • Java 알고리즘 공부 (37)
      • Java 백준 문제풀이 (27)
      • Java 코테 나만의 팁 (3)
    • SQL Study (0)
      • Programmers SQL 문제풀이 (0)
      • SQLP 준비 (0)
    • 웹 개발 지식 정리 (0)
      • Servlet (0)
      • Java 정리 (0)
    • 자바 스프링 (45)
      • 스프링 공부 (4)
      • 스프링 게시판 프로젝트 (6)
      • 부트 블로그 JPA 프로젝트 (30)
      • react & springboot (5)
      • 스프링 오류창고 (0)
      • 리액트 + 스프링 프로젝트 (0)
      • pf (0)
      • pfError (0)
    • React (6)
      • React 정리 (3)
      • React 오류 창고 (3)
    • C++ 코딩테스트 공부 (중단) (20)
      • c++ 백준 문제풀이 (15)
      • c++ 알고리즘 공부 (5)
    • Unity (3)
      • Unity 공부 (3)
    • WebRTC (2)
      • WebRTC 강의학습 정리 (0)
      • WebRTC 프로젝트 (1)
    • 김영한님의 스프링 강의 학습 (10)
      • 스프링 강의 목차 (1)
      • 인텔리제이 & 스프링 기초 (1)
      • 스프링 핵심 원리 (8)
    • 전공 지식 정리 (40)
      • interview (0)
      • Java (0)
      • 운영체제 (4)
      • 데이터베이스 설계 (10)
      • 소프트웨어 공학 (3)
      • 유닉스 (14)
      • 디지털 논리회로 (0)
      • 인공지능 (7)
      • js (0)
      • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 디지털 논리회로
  • 스프링부트 블로그 프로젝트
  • 김영한 스프링 입문
  • 운영체제
  • 김영한 스프링 강의
  • 데이터베이스 설계
  • Unity 공부
  • java 알고리즘
  • React&Spring 강의수강
  • Java 백준 문제풀이
  • Java 코테 나만의 팁
  • C++ 알고리즘
  • 코테 알고리즘
  • 부트 jpa 게시판 프로젝트
  • 백준 c++
  • java
  • 무서운 이야기
  • 김영한의 스프링 핵심 원리
  • 스프링부트 프로젝트
  • 유닉스
  • 스프링 프로젝트
  • 인공지능
  • 스프링 공부
  • 노마드코더의 zoom클론코딩

최근 댓글

최근 글

hELLO · Designed By 정상우.
daramG
Recursive, Tree, Graph(DFS, BFS 기초) 2 - 이진트리, 부분집합 DFS
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.