Chapter 07. Recursive, Tree, Graph (DFS, BFS 기초)

자료구조와 알고리듬 With Java/[인프런] Algorithm

Chapter 07. Recursive, Tree, Graph (DFS, BFS 기초)

계란💕 2022. 4. 15. 16:36

1. 재귀함수 (스택 프레임)

java

열기

public class Main {
  public void DFS(int n){
    if(n == 0) return;
    else{
    	System.out.println(n);
    	DFS(n-1);
    }
  }
  
  public static void main(String[] args){
    Main T = new Main();
   	T.DFS(5);
    return ;
  }
}

Note)

- 실행 결과: 5 4 3 2 1 츨력

2. 이진수 출력 (재귀)

java

열기

import java.util.Scanner;
public class Main {
  public void DFS(int n){
  	
    if(n == 0) return;
    else{
    	System.out.print(n + " ");
    	DFS(n / 2);
    }
  }
  
  public static void main(String[] args){
    Main T = new Main();
   	T.DFS(11);
    return ;
  }
}

Note) 실행결과

3. 팩토리얼

java

열기

import java.util.Scanner;
public class Main {
  
  public int DFS(int n){
    if(n == 1) return 1;
    else return n * DFS(n - 1);
  }
  
  public static void main(String[] args){
    Main T = new Main();
   	System.out.println(T.DFS(5));
    return ;
  }
  
}

Note) 실행 결과 : 120

- 5! = 5 * 4 * 3 * 2 * 1의 결과인 120이 출력된다.

4. 피보나치 재귀 (메모이제이션)

java

열기

import java.util.Scanner;
public class Main {

  static int [] fibo;
  public int fibonacci(int n){
    if(n == 1 || n == 2) return fibo[n] =  1;
    else return fibo[n] = fibonacci(n - 2) + fibonacci(n - 1);
  }
  
  public static void main(String[] args){
    Main T = new Main();
    int n = 10;
    fibo = new int[n + 1];
    T.fibonacci(n);
    for(int i = 1; i <= n ; ++i){
 	  	System.out.print(fibo[i] + " ");   	
    }
    return ;
  }
}

Note) 실행 결과: 1 1 2 3 5 8 13 21 34 55

- 배열과 for문으로 짜는 것이 재귀함수로 돌리는 것보다 성능이 좋다. (재귀를 돌리기에는 무겁다.)

-> 재귀는 호출될 때마다 스택에 프레임이 생기기 때문이다.

- 중소기업의 코딩테스트 질문으로 많이 나오기도 한다.

- static int 배열을 만들어 배열에 기록해두고 출력할 수 있다.

- 기록해두는 것을 "메모이제이션"이라고 한다.

- 메모이제이션을 활용하면 시간 복잡도가 확 줄어든다.

5. 이진트리순회(DFS : Depth-First Search)

Note)

- 전위 순회: 부모 -> 왼쪽 자식 -> 오른쪽 자식

- 중위 순회: 왼쪽 자식 -> 부모 -> 오른쪽 자식

- 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 부모

(1) 전위순회

java

열기

import java.util.*;
class Node{
	int data;
  	Node lt, rt;
  
  public Node(int val){
  		data = val;
   		lt = rt = null;		//객체가 생성되는 순간 null 값
  }
}
  
public class Main {
  
  Node root;
  public void DFS(Node root){
  		if(root == null) return;
    	else{
          	System.out.print(root.data + " ");
        	DFS(root.lt);
        	DFS(root.rt);
        }
  }
  
  public static void main(String[] args){
    Main tree = new Main();
    tree.root = new Node(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);
  }
  
}

Note) 전위순회 실행 결과 : 1 2 4 5 3 6 7

(2) 중위 순회

java

열기

import java.util.*;
class Node{
	int data;
  	Node lt, rt;
  
  public Node(int val){
  		data = val;
   		lt = rt = null;		//객체가 생성되는 순간 null 값
  }
}
  
public class Main {
  
  Node root;
  public void DFS(Node root){
  		if(root == null) return;
    	else{
          	DFS(root.lt);
          	System.out.print(root.data + " ");
        	DFS(root.rt);
        }
  }
  
  public static void main(String[] args){
    Main tree = new Main();
    tree.root = new Node(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);
  }
}

Note) 중위순회 실행 결과 : 4 2 5 1 6 3 7

(3) 후위순회

java

열기

import java.util.*;
class Node{
	int data;
  	Node lt, rt;
  
  public Node(int val){
  		data = val;
   		lt = rt = null;
  }
}
  
public class Main {
  
  Node root;
  public void DFS(Node root){
  		if(root == null) return;
    	else{
          	DFS(root.lt);
          	DFS(root.rt);
          	System.out.print(root.data + " ");
        }
  }
  
  public static void main(String[] args){
    Main tree = new Main();
    tree.root = new Node(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);
  }
}

Note) 후위순회 실행 결과 : 4 5 2 6 7 3 1

6. 부분집합 구하기 (DFS)

java

열기

import java.util.*;
public class Main {
  static int n;
  static int[] ch;
  public void DFS(int L){
  	if(L == n + 1){
    	String tmp = "";
      	for(int i = 1; i <= n; ++i){
        	if(ch[i] == 1) tmp += (i + " ");	
          	// 자동으로 string형 변환
        }
    	if(tmp.length() > 0) System.out.println(tmp);     
    }else{
      	ch[L] = 1;	// 사용한다는 의미로 '1'표시
    	DFS(L + 1); 	// 왼쪽으로 뻗는다.
        ch[L] = 0;
   		DFS(L + 1);	// 오른쪽으로 뻗는다.
    }
  }
  
  public static void main(String[] args){
    Main T = new Main();
   	n = 3;
    ch = new int[n + 1];
    T.DFS(1); 
  }
}

Note) 실행 결과

- 재귀함수, back tracking, BFS 코딩 테스트에 자주 나오니 꼭 해봐야한다.

????

7. 이진트리 레벨탐색(BFS : Breadth-First Search)

java

열기

import java.util.*;
class Node{
	int data;
  	Node lt, rt;
  
  public Node(int val){
  		data = val;
   		lt = rt = null;
  }
}
  
public class Main {
  
  Node root;
  
  public void BFS(Node root){
  	Queue<Node> Q = new LinkedList<>();
    Q.offer(root);
    int L = 0; // level 
    while(!Q.isEmpty()){
    	int len = Q.size();
      	System.out.print(L + " : ");
    	for(int i = 0 ; i < len; ++i){
          	Node cur = Q.poll();
          	System.out.print(cur.data + " ");
          	if(cur.lt != null) Q.offer(cur.lt);
        	if(cur.rt != null) Q.offer(cur.rt);
        }
      	L++; // 레벨 증가
      	System.out.println();
    }
  }
  
  public static void main(String[] args){
    Main tree = new Main();
    tree.root = new Node(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.BFS(tree.root);
  }
}

Note) 실행 결과

- 너비 우선 탐색 (BFS)

- 0 레벨 : 1 ( root) / 1레벨 : 2 3 (root에서 한 번에 이동 가능) / 3레벨: 4 5 6 7 (root에서 두 번 만에 간다.)

-> 즉, root로부터의 거리라고 볼 수 있다.

- 다음 문제인 송아지 찾기 이해하려면 꼭 알아야한다.

8. 송아지 찾기1(BFS - 상태 트리 탐색)

java

열기

import java.util.*;
  
public class Main {
  int answer = 0;
  int [] dis = {1, -1, 5};	// 전진, 후진
  int[] ch;	//방문 여부 체크 배열 , 0이면 방문하지 않은 곳
  Queue<Integer> Q = new LinkedList<>();
  
 public int BFS(int s, int e){
 	ch = new int[10001];	// 직선 좌표의 최댓값 10000
 	ch[s] = 1;
   	Q.offer(s);
 	int L = 0;	// root node는 level이 0
   	while(!Q.isEmpty()){
   		int len = Q.size();	// level에 있는 원소의 개수
   		for(int i = 0; i < len; ++i){
        	int x = Q.poll();
          	for(int j = 0; j < 3; ++j){	//
            	int nx = x + dis[j];	// x의 자식노드를 찾는다.
              	if(nx == e)	return L + 1;	
              	// 자식 노드니까 1 더하기	
              	if(1 <= nx && nx <= 10000  && ch[nx] == 0 ){
                	ch[nx] = 1;		// 방문 체크
                  	Q.offer(nx);	// 체크 후 Q에 넣는다.
                }
            }
        }
      	L++;	//	level 증가
	 }
   return 0;
 }
  
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int s = in.nextInt(); 	// 현수의 위치
    int e = in.nextInt();	// 송아지의 위치
    System.out.println(T.BFS(s, e));
    return ;
  }
}

Note)

- 레벨은 점프 횟수라고 볼 수 있다.

- 최초로 발견되는 것이 최단거리

- 중복되는 수는 없다.

- 3level에서 최초로 14가 발견된다.

9. Tree 말단 노드까지의 가장 짧은 경로 (DFS)

java

열기

import java.util.*;
class Node{
	int data;
  	Node lt, rt;
  
  public Node(int val){
  		data = val;
   		lt = rt = null;		//객체가 생성되는 순간 null 값
  }
}
  
public class Main {
  
  Node root;
  public int DFS(int L, Node root){	
  // root가 가리키는 말단 노드, level, 이동거리
  		if(root.lt == null && root.rt == null) return L;	
    	//root가 말단 노드인지 확인
    	
    	else return Math.min(DFS(L + 1, root.lt), DFS(L + 1, root.rt));
        // 말단 노드가 아닐 때
          
  }
  
  public static void main(String[] args){
    Main tree = new Main();
    tree.root = new Node(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);
   	System.out.println(tree.DFS(0, tree.root));
    
  }
}

Note) 실행 결과: 1

- 경로의 길이 : 루트 -> 말단 노드까지 가는데 이동하는 횟수, (간선의 개수)

- 최단거리문제 -> BFS로 푼다.

-> DFS로 풀 수는 있지만 제약이 있다. (자식 노드가 하나만 있을 때 에러가 나기 때문이다.)

10. Tree 말단 노드까지의 가장 짧은 경로 (BFS)

java

열기

import java.util.*;
class Node{
	int data;
  	Node lt, rt;
  
  public Node(int val){
  		data = val;
   		lt = rt = null;		//객체가 생성되는 순간 null 값
  }
}
  
public class Main {
  
  Node root;
  public int BFS(int L, Node root){	
  	Queue<Node> Q = new LinkedList<>();
    Q.offer(root);
    int L = 0;
    while(!Q.isEmpty()){
    	int len = 0;
      	for(int i = 0; i < len; ++i){
        	Node cur =  Q.poll();
          	if(cur.lt == null && cur.rt == null )return L;
          	if(cur.lt != null) Q.offer(cur.lt); // 왼쪽 자식이 있을 때 넣어준다. 
          	if(cur.rt != null) Q.add(cur.rt);	//add offer 상관없음
        }
      	++L;
    }
   	return 0;
  }
  
  public static void main(String[] args){
    Main tree = new Main();
    tree.root = new Node(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);
   	System.out.println(tree.BFS(0, tree.root));
    
  }
}

Note) 실행 결과 : 1

11. 그래프와 인접행렬

- G(V, E) : G:그래프, V: vertax, E: edge

- 인접행렬: 연결된 노드에 대해 1로 표시, 연결되있지 않으면 0으로 표시한다.

1) 무방향 그래프

- 방향 개념이 없다.
- graph[a][b]와 graph[b][a] 에 모두 1 표시한다.

2) 방향 그래프

- 이동하는 방향이 정해져 있다.

- 행 -> 열로 해석한다.

3) 가중지 방향 그래프

- 간선에 가중치 까지 있다. (ex) 비용)

- graph[a][b] = 3 : a -> b로 가는데 가중치는 3이다.

12. 경로 탐색 (DFS) - 방향그래프가 주어지면 1번 -> N번 정점으로 가는 모든 경우의 수 출력

- 1번 노드 -> 5번까지 가는 경로

- 12345

- 125

- 13425

- 1345

- 1425

- 145

java

열기

import java.util.*;
public class Main {
  static int n, m , answer = 0;
  static int[][] graph;
  static int[] ch; // 방문 여부 체크
  
  public void DFS(int v){
  		if (v == n) answer++;
    	else{	// 가능한 곳으로 계속 뻗어 나간다.
         	for(int i = 1; i <= n ; ++i){
            	if(graph[v][i] == 1 && ch[i] == 0){
                	ch[i] = 1;
                  	DFS(i);		
                  	ch[i] = 0;	// 취소 (체크를 풀어준다.)
                
                }
            }
        }
  }
  
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    m = in.nextInt();
    graph = new int[n+1][n+1]; // 인덱스 1 ~ n까지 쓰려고
    ch = new int[n+1];
    for(int i = 0; i < m; ++i){
    	int a = in.nextInt();
      	int b = in.nextInt();
      	graph[a][b] = 1;	// 방향 그래프
    }
    ch[1] = 1;	// 1번 노드 출발점 표시
    T.DFS(1);	// 
    System.out.println(answer);
  }
}

Note) 실행 결과

- 경로에서 방문 했던 곳은 방문하지 않는다.

- 노드 개수만큼 for문이 돈다.

- back할 때는 체크를 하나씩 풀어준다.

13. 경로탐색 (인접리스트, ArrayList)

- 1번 노드 -> 5번까지 가는 경로

- 12345

- 125

- 13425

- 1345

- 1425

- 145

// 오류

5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

java

열기

package first;
import java.util.*;
public class Main3 {
  
		static int n, m, answer=0;
		static ArrayList<ArrayList<Integer>> graph;
		static int[] ch;
		public void DFS(int v){
			if(v==n) answer++;
			else{
				for(int nv : graph.get(v)){
					if(ch[nv]==0){
						ch[nv]=1;
						DFS(nv);
						ch[nv]=0;
					}
				}
			}
		}
		
		public static void main(String[] args){
			Main T = new Main();
			Scanner kb = new Scanner(System.in);
			n=kb.nextInt();
			m=kb.nextInt();
			graph = new ArrayList<ArrayList<Integer>>();
			for(int i=0; i<=n; i++){
				graph.add(new ArrayList<Integer>());
			}
			ch=new int[n+1];
			for(int i=0; i<m; i++){
				int a=kb.nextInt();
				int b=kb.nextInt();
				graph.get(a).add(b);
			}
			ch[1]=1;
			T.DFS(1);
			System.out.println(answer);
		}	
	
  
}

Note)

- 정점의 개수가 많으면 ArrayList<>를 이용한다.

14. 그래프 최단거리(BFS) - 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간건 수를 출력

java

열기

import java.util.*;
class Main {
	static int n, m, answer=0;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] ch, dis;
	public void BFS(int v){
		ch[v]=1;		// 1번에서 시작
		dis[v]=0;		// 출발 지점: 0
		Queue<Integer> queue=new LinkedList<>();
		queue.offer(v);	
		while(!queue.isEmpty()){
			int cv=queue.poll();	//cv: current vertax (현재 지점)
			for(int nv : graph.get(cv)){
				if(ch[nv]==0){	// 방문 안 했으면 
					ch[nv]=1;
					queue.offer(nv);
					dis[nv]=dis[cv]+1; 
				}
			}
		}
	}
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();	// 정점 개수
		m=kb.nextInt();	// 간선 개수
		graph=new ArrayList<ArrayList<Integer>>();
		for(int i=0; i<=n; i++){
			graph.add(new ArrayList<Integer>());
		}
		ch=new int[n+1];
		dis=new int[n+1];
		for(int i=0; i<m; i++){	// 인접 list 만든다.
			int a=kb.nextInt();
			int b=kb.nextInt();
			graph.get(a).add(b);
		}
		T.BFS(1);	// 1번 부터 시작한다.
		for(int i=2; i<=n; i++){	// 2번 부터 출력
			System.out.println(i+" : "+dis[i]);
		}
	}	
}

Note)

- 최단거리 = BFS문제 라고 본다.

- dis[v]: v까지 가는 최소 거리

- dis[nv] = dis[v] + 1

-입력

6 9

1 3

1 4

2 1

2 5

3 4

4 5

4 6

6 2

6 5

-출력

2 : 3

3 : 1

4 : 1

5 : 2

6 : 2

-> 2 : 3 => 3 ( 1 -> 4 -> 6 -> 2)

-> 3 : 1 => 1 (1 -> 3)

-> 4 : 1 => 1 (1 -> 4)

-> 5 : 1 (1 ->4 -> 5 )

저작자표시

'자료구조와 알고리듬 With Java > [인프런] Algorithm' 카테고리의 다른 글

Chapter 08. DFS, BFS 활용 (0)	2022.04.18
Chapter 06. Sorting and Searching (정렬, 이분검색과 결정알고리즘) (0)	2022.04.14
Chapter 05. Stack, Queue (자료구조) (0)	2022.04.13
Chapter 04. HashMap, TreeSet (해쉬, 정렬지원 Set) (0)	2022.04.12
Chapter 03. Two pointers, Sliding window (0)	2022.04.12

현재글Chapter 07. Recursive, Tree, Graph (DFS, BFS 기초)

Backend Developer lan4250@naver.com https://github.com/goraneee

BFS, GIT, 제로베이스 백엔드, 코드업, Java, DB, JPA, 스프링, SQL, 알고리즘, 데이터베이스, Queue, dfs, 백준, Stack, dp, mysql, 제로베이스 스쿨, 프로그래머스, 자바,

Today :
Yesterday :

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

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

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

계란 블로그