[TIL]20230622 - 재귀함수와 DFS

평소 알고리즘문제를 풀면서 미로찾기 등 재귀함수 및 DFS를 사용하는 문제 풀이에 어려움이 있었다. 그래서 오늘은 알고리즘 주차 마지막인만큼 오늘 이 문제를 조금이라도 해결해보고자 재귀함수와 DFS에 대해 공부해보았다.

우선 재귀함수란 함수 안에 자기 자신의 함수를 호출하는 함수이다.

재귀함수는 종료조건이 없으면 무한대로 실행되게 되므로 반드시 종료조건을 만들어주어야한다.

public static void HelloWorld(int n){
		// n이 0인 경우 return
		if(n == 0)
			return;
		
		System.out.println("HelloWorld"); // HelloWorld 출력
		HelloWorld(n-1); // 재귀함수 시작
}

위 함수는 Helloworld를 반복해서 출력하는 재귀함수이다.

반복할 int n을 넣어 함수를 호출하게 되면 우선 종료 조건에 대해 검사하고 맞다면 리턴을 통해 함수를 종료시킨다. 종료 조건에 부합하지 않는다면 Helloworld를 촐력하고 입력받은 n을 1만큼 감소시켜 다시 호출하게 된다.

계속해서 재귀적으로 호출되다보면 n은 0이 된채로 호출되게 될것이고 그렇다면 return을 통해 더이상 출력되지 않을것이다.

다음으로 DFS이다.

DFS(Depth-First Search)는 깊이우선탐색으로 그래프를 탐색하는 방법 중 하나이다. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법으로 탐색과정은 다음과 같다.

프로그래머스 중 DFS를 사용하는 문제를 한번 풀어보았다.

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

이 문제에서 루트 노드가 0이고 노드마다 2개의 자식노드를 가지게되고 각각 부모노드에서 +배열의 값, -배결의 값 을 가지게된다. 최종적으로 생성되는 그래프(트리 구조)는 트리의 깊이가 입력된 배열의 크기인 완전 이진트리가 된다.

그리고 answer를 증가 시키는 조건은 depth가 배열의 길이, 즉 트리의 맨 마지막에 도달했을때 그 노드의 숫자가 target과 같다면 answer를 증가시킨다.

작성한 코드는 다음과 같다.

class Solution {
    int answer = 0;

    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target, 0);
        return answer;
    }
    public void dfs(int[] numbers, int depth, int target, int sum){
        //종료조건
        if(depth == numbers.length){
            //정답 조건
            if(target == sum)
                answer++;
        }
        if(depth < numbers.length){
            dfs(numbers, depth + 1, target, sum + numbers[depth]);
            dfs(numbers, depth + 1, target, sum - numbers[depth]);
        }

    }
}

dfs함수 내에서 종료 조건을 통해 조건을 확인하고 종료가 아니라면 깊이를 1 증가시키고 배열의 값만큰 + , - 하여 자식 노드를 생성하여 트리를 늘려나간다.
마침내 depth가 배열의 길이 만큼 된다면 그 노드가 target과 같은지 검사 후 같다면 answer를 1증가시킨다.