섹션 7. DFS, BFS 기초 섹션 - (1) 재귀 함수와 DFS

재귀 함수 (Recursive Function)

• 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수
• 함수 내에서 자기 자신을 다시 호출하는 방식
• [주의] 무한 루프에 빠지지 않도록 주의하며 작성할 것

⬛ 스택 프레임 기반

재귀함수는 스택 프레임

DFS(n-1) 밑에 print 찍으면 다음과 같이 스택이 쌓이게 된다.

• ‘복귀 주소’ : DFS()의 함수내용을 전부 실행한 후 스택프레임이 사라지면서 자기가 호출되었던 주소로 복귀한다.

---

◼️ 1번. 재귀함수 (스택 프레임) | DFS

문제 설명

🟦 문제 풀이

풀이 설명

• N이 입력되면 DFS(N)을 호출한다.
• DFS()함수가 최초로 호출된 시점에서 N 부터 1씩 감소하면서 깊이 탐색을 한다.
• 만약 N값이 0이되면 return 해주는데, 반환 시점에서 출력해주면 차례대로 1, 2, 3 이 출력되는 것을 확인할 수 있다. | 스택 성질

🟦 코드

import java.util.Scanner;

/**
 * 재귀함수 - DFS
 * @author MYLG
 *
 */
public class Main {
	
	static void DFS(int N) { 
		if(N == 0)return;
		else {
			DFS(N-1); 
			
			System.out.print(N + " ");
		}
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		DFS(N); //최종
	}

}

---

◼️ 2번. 재귀함수로 이진수 출력

문제 설명

🟦 문제 풀이

• 10진수를 2진수로 만들 때 가장 핵심은 2로 나눈 나머지를 역순으로 출력하는 거다.
• N = 11이기 때문에 DFS(11)이 호출되면 → D(11/2) → D(5/2) → D(2/2) → D(1/2) 이런 식이다.
• 이떄 나머지는 1, 1, 0, 1 로 되는데 복귀 시 출력하도록 하면, 역순 출력이 가능하므로 1 0 1 1 의 답이 정상적으로 나올 수 있게 된다.

🟦 코드

/**
 * 재귀함수 이용하여 이진수 출력 
 */
import java.util.Scanner;

public class Main {
	//DFS
	static void DFS(int N) {
		if(N == 0) return;
		else {
			DFS(N/2);//몫으로 계속 가주고 
			
			//반환 시점에서 
			System.out.print(N%2+" ");
		}
		
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		DFS(11);
	}
}

---

◼️ 3번. 팩토리얼

문제 설명

🟦 문제 풀이

• 여기서 DFS(), 재귀함수가 필요한 이유는 N! 가 N X N-1 … X 1 을 상징하기 때문이다.
• 재귀로 DFS(N)을 입력받으면 복귀 시점이든 호출 시점이든 정해서 하나씩 감소한 다음 깊이의 N-1을 탐색하도록 차례로 가면 된다.
• 물론 여기서 답을 주관할 answer는 0이 아닌 1로 초기화해야 한다.
• DFS(5) → DFS(4) → DFS(3) → DFS(2) → DFS(1) → DFS(0) 반환
• (0으로 초기화하면 뭘 곱해도 0 이므로 초기화 시 주의)

🟦 (1) “호출 시점”에서 답 구하기

import java.util.Scanner;

/**
 * 팩토리얼 
 * @author MYLG
 *
 */
public class Main {
	static int answer = 1;
	//DFS
	static void DFS(int val) {
		if(val == 0) return;
		else {
			answer *= val;
			DFS(val - 1);
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		
		DFS(N);
		System.out.println(answer);
	}
}

🟦 (2) “반환 시점”에서 답 구하기

import java.util.Scanner;

/**
 * 팩토리얼 
 * @author MYLG
 *
 */
public class Main {
	static int answer = 1;
	//DFS - 반환 시점에서 답 구하기 
	static void DFS(int val) {
		if(val == 0) return;
		else {
			//호출 시점 
			DFS(val - 1);
			//반환 시점
			answer *= val;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		
		DFS(N);
		System.out.println(answer);
	}
}

---

◼️ 4번. 피보나치 수열

문제 설

🟦 문제 풀이

• 3번째 항부터 a1 + a2 = a3 인 규칙이 생긴다.
• 따라서 a1 = 1. a2 =1 을 초기화 해두어야 한다.
• 항의 개수는 N으로 입력받은 수준까지 뻗도록 해야 한다.
• arr[] 배열을 생성하여 각 lv에 맞는 항의 값을 저장해주고, DFS 더 깊이 탐색을 시도하면 된다.

🟦 코드

import java.util.Scanner;

/**
 * 피보나치 수열 - 
 * @author MYLG
 *
 */
public class Main {
	static int N;
	static int[] arr;
	//DFS
	static void DFS(int lv) {
		if(lv == N + 1) return;
		else {
			arr[lv] = arr[lv-1] + arr[lv-2];
			DFS(lv+1);
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		N = kb.nextInt();
		//총 항의 수 
		arr = new int[N + 1];
		arr[1] = 1;
		arr[2] = 1;
		DFS(3);
		
		for(int i=1; i<=N; i++) {
			System.out.print(arr[i] +  " ");
		}
	}
}