Java DFS 기초 이해와 문제 풀이

개요 목적

DFS 깊이 우선 탐색을 재귀 함수로 많이 표현하기 때문에 재귀 함수 동작 과정을 먼저 이해해야 한다.

아래 문제들을 풀면서 재귀 함수가 어떻게 진행되는 지 파악하면서 공부해보자.

그리고 기초적인 DFS 문제들을 풀면서 DFS에 대한 이해를 해보자.

재귀 함수 문제 풀이

1. 해당 재귀 함수가 어떻게 진행될까 생각해보기

public class Main {
    public static void DFS(int n) {
        if (n == 0) {
            return;
        } else {
            DFS(n - 1);                //6번 라인
            System.out.print(n + " "); //7번 라인
        } 
    }
    public static void main(String[] args){
				DFS(3);
    }
}

DFS(3) 에서 6번 라인에 DFS(n-1) 때문에, DFS(3)은 7번 라인이 실행 되길 기다리면서 스택에 쌓인다. 이런 방식으로 DFS(0)까지 쌓이게 되고,

DFS(0)은 return으로 스택에서 완전히 빠져나가 7번 라인 실행을 기다리는 DFS(1)이 실행된다.

그리고 DFS(1) System.out.println으로 메소드가 끝나고, 7번 라인 실행을 기다리는 DFS(2)이런 식으로 진행 되면서 스택에 있는 모든 DFS 메소드가 호출되면서 끝나게 된다.

2. 이진수를 출력하는 재귀 함수 사용

public class 재귀이진수출력 {
    public static void DFS(int n) {
        if (n == 0) {
            return;
        } else {
            DFS(n / 2);
            System.out.print(n%2);
        }
    }
    public static void main(String[] args) {
        DFS(11);
    }
}

n=11 부터 6번에 있는 재귀함수를 통해서 7번이 실행되길 기다리면서 DFS(5)를 실행한다. 이런 스택 구조가 쌓여간다.

DFS(0)이 return 되면서 DFS(1)의 7번 라인이 실행되고 DFS(1)이 끝난 후에 DFS(2)가 7번라인 실행한다.

이런 식으로 DFS(11) 까지 System.out.print(n%2)가 실행해서 1011을 출력할 수 있게된다.

3. 팩토리얼 재귀함수 사용하기 returun 값을 활용

public class 재귀팩토리얼 {
    public static int DFS(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * DFS(n - 1);
        }
    }
    public static void main(String[] args) {
        System.out.println(DFS(5));
    }
}

DFS(5)일 때, retrun 5DFS(4)를 하려고 했더니, DFS(4)의 리턴값이 아직 없다.

그래서 타고 타고 올라 가서 DFS(1) 1을 retrun하고, DFS(2)는 21 =2 를 리턴하고, DFS(3)은 3*2 =6을 리턴하고

DFS(5)가 찾던 DFS(4)는 46 =24를 리턴 한다. 그 값을 받아서 DFS(5)의 리턴 5DFS(4) = 5*24 = 120이라는 최종 리턴 값을 출력한다.

4. 피보나치 수열 재귀 함수 사용(배열을 사용해서 시간 줄이기)

import java.util.Arrays;

public class 재귀피보나치수열 {

    static int[] arr = new int[11];
    public static int DFS(int n) {
        if (arr[n] > 0) {
            return arr[n];
        }
        if (n == 1) {
            return arr[1] = 1;
        } else if (n == 2) {
            return arr[2] =1;
        } else {
            return arr[n] = DFS(n - 1) + DFS(n - 2);
        }
    }
    public static void main(String[] args) {
        DFS(10);
        System.out.println(Arrays.toString(arr));
    }
}
//if (arr[n] > 0)  이미 구한 값이 있다면, 아래로 타고 내려가지 않고, 바로 그 값을 리턴한다.

아래 그림 같은 모양 DFS 스택을 사용해서 DFS(10)을 구하면 되는 문제다.

여기에 기존에 구한 값은 배열에 저장해서 시간을 줄일 수 있다.

예를 들어 아래 그림에서 D(4) = D(2)+D(3)을 구할 때 이미 왼쪽에서 D(3)이라는 값을 구했기 때문에, 아래로 타고 내려가는 재귀를 거치지 않아도 된다.

5. 이진트리 순회하기

전위순회 - 부모→왼쪽 → 오른쪽 (부모를 먼저)

1 2 4 5 3 6 7

중위순회 - 왼쪽→부모→오른쪽

왼쪽 자식부터 4 2 5 1 6 3 7

후위순회 - 왼쪽→오른쪽→부모

4 5 2 6 7 3 1

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{
            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[]) { 
        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); 
    } 
}

DFS 기초적인 문제 풀어보기

1. 부분 집합 구하기

import java.util.Scanner;

public class 부분집합구하기 {

    static int[] ch;
    static int n;

    public static void DFS(int l) {
        if (l == n + 1) {
            String str = "";
            for (int i = 1; i < ch.length; i++) {
                if (ch[i] == 1) {
                    str += i;
                }
            }
            System.out.println(str);
        } else {
            ch[l] = 1;
            DFS(l + 1);
            ch[l] = 0;
            DFS(l + 1);
        }
    }
    public static void main(String[] args){
        n = 3;
        ch = new int[n + 1];
        DFS(1);
    }
}

양쪽으로 뻗어지는 데 한쪽은 ch[l] =1 있는 쪽으로 다시 돌아와서는 ch[l]=0 없는 쪽으로 설정한 후에 DFS() 양쪽 방향으로 뻗어지게 한다.

2. 트리 말단노드까지 가장 짧은 경로 DFS

public class 말단노드까지가장짧은경로 {
    static class Node{
        int data;
        Node lt, rt;
        public Node(int val) {
            data=val;
            lt=rt=null;
        }
    }
    static int answer = 0;

    public static int DFS(Node node, int L) {
        if (node.lt == null && node.rt == null) {
            return L;
        } else {
            return Math.min(DFS(node.lt, L + 1), DFS(node.rt, L + 1));
        }
    }
    public static void main(String[] args) {
        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);
        System.out.println(DFS(root, 0));
    }
}

마지막에, D(0,root) 는 D(1,2)=2 값과 D(1,3)=1 값 중에서 더 작은 값을 선택 하게 된다.

즉 가장 가까운 값이 3인 말단 노드까지 거리인 1이 답이 된다.