20240328_DFS(타겟 넘버)

오늘의 TIL은 DFS에 대한 내용이다.

 

DFS(Depth First Search - 깊이 우선 탐색)

DFS는 그래프 탐색 알고리즘에서 사용되는 개념인데

여기서 그래프는 여러 개체들이 연결되어 있는 자료 구조이고

탐색은 특정 개체를 찾을 때 사용하는 알고리즘이다.

즉, DFS는 여러 개체들이 연결되어 있는 상태에서 특정 개체를 찾는데 사용하는 방법으로

깊이 우선 탐색(한 노드에서 끝까지 탐색)하는 방법이다.

 

아래 이미지처럼 왼쪽 노드부터 오른쪽 노드로 가는 순서로 탐색을 만들었다면

왼쪽 마지막 노드까지 탐색한 후에 오른쪽으로 한 칸 가서 탐색을 반복한다.

DFS의 탐색 순서를 나타내는 이미지

 

 

 

DFS는 대표적으로 아래의 문제를 풀 때 사용한다.

1. 최단거리, 최소시간을 구하는 경우

2. 연결되는 그룹의 개수를 구하는 경우

3. 모든 조합을 만드는 경우

 

DFS는 일반적으로 한 노드를 끝까지 탐색하는 방법이므로

재귀 함수로 구현하는 것이 일반적이다.

 

 

DFS 문제 예시

이전에 풀이했던 타겟 넘버를 예로 들어서 이해하면

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

프로그래머스

 

using System;

public class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = FindTarget(numbers, target);
        
        return answer;
    }
    static public int FindTarget(int[] numbers, int target)
    {
        return DFS(numbers, 0, 0, target);
    }

    static private int DFS(int[] numbers, int index, int sum, int target)
    {
        if (index == numbers.Length)
        {
            if (sum == target)
            {
                return 1;
            }
            return 0;
        }

        int add = DFS(numbers, index + 1, sum + numbers[index], target);
        int subtract = DFS(numbers, index + 1, sum - numbers[index], target);

        return add + subtract;
    }
}

 

타겟 넘버의 문제를 간략히 설명하면

배열 numbers로 주어지는 숫자들을 가지고 더하거나 빼서 target으로 주어지는 숫자를 만드는 알고리즘 문제이다.

 

이는 위와 같이 문제를 풀이할 수 있는데 DFS 부분을 살펴보면

if 문으로 해당 노드의 끝까지(index가 numbers의 길이까지) 탐색했는지 확인하고

이 경우에 더하거나 뺀 값이 target과 같은지 확인하여

같다면 1(유효한 조합을 찾음), 다르다면 0(유효한 조합을 찾지 못함)을 반환한다.

 

index가 아직 numbers의 길이에 도달하지 않았다면

int로 선언한 add와 subtract를 통해 다음 index의 수를 더하고 빼는 DFS를 연결하여 재귀를 구현한다.

그 후에 그 결과를 합쳐서 반환하는데

이는 현재 위치에서 시작하여 타겟 숫자를 만들 수 있는 모든 조합의 수를 의미한다.

 

 

위와 같은 방식으로 DFS의 기본 정보를 알아보고 정리하고

이전에 풀이했던 '타겟 넘버'의 코드를 다시 보면서 DFS를 공부했는데

'양과 늑대' 문제와 '타겟 넘버' 문제를 풀면서 DFS를 정리하는 기회를 가졌다.

자료구조에서 그래프, DFS, BFS 등을 사용하는 문제에 약했는데

이번 기회에 이들에 대해 정리하고 공부할 수 있는 기회를 가졌다.