[알고리즘] 자바로 DFS(깊이 우선탐색) 쉽게 이해하기 [구현까지]

[목차]

 

dfs란 코딩 테스트에서 빠질 수 없는 단골문제 알고리즘입니다.

기본적으로 재귀함수를 이용해 모든 경우의 수를 탐색하는 방법이고

처음에 dfs접하면 재귀함수가 어려워 난해한 알고리즘입니다.

 

 

 

[DFS란?]

 

DFS란 깊이 우선 탐색이라하며

기본적으로 그래프 형식으로 가지를 계속 뻗어나가 모든 경우의 수를 찾는 알고리즘 입니다.

 

DFS의 경우 여러가지가 있지만 대표적으로 순열 , 중복순열 , 부분 순열등이 있습니다.

 

[순열과 중복순열이란?]

 

1. 순열은 쉽게 N개의 조합을 사용 할 때 중복된 값들을 제외 하고 모든 경우의 탐색을 하는 방법 입니다.

 

즉 쉽게 생각한다면 카드 [1,2,3,4,5]라는 카드가 있으면

 

이 카드 N개를 뽑을 때 이 카드의 가장 큰 값을 구해라 라는 이런 문제가 순열의 해당됩니다.

 

즉 3개의 카드를 뽑았을 때 가장 큰 값을 찾아라 한다면

 

[1,2,3] [1,2,4] [1,2,5]

[2,1,3] ... 등 이런 모든 경우의 수 가 있습니다.

 

이 경우에는 중복된 값들을 가져오는게 아니죠?

카드 하나씩 뽑아서 가장 큰 값을 찾는거니 카드를 뽑을 때는 중복된 카드를 뽑을 수 없습니다.

이것이 순열입니다.

모든 카드의 경우의 수를 찾되 이 조합은 겹치면 안되는 경우가 순열입니다.

 

중복 순열의 경우 

순열과 비슷하지만 모든 중복된 경우의 수를 찾는 방법입니다.

모든 경우의 수를 찾되 중복된 결과도 포함해서 찾는 결과 입니다.

 

굳이 재귀함수 안에서 반복문을 사용하지 않아도 되지만 그것까지 적기엔

너무 양이 많기 때문에 제 DFS문제를 보며 감을 익히는 것을 추천드립니다.

 

 

 

여기 백준문제 5568카드 놓기라는 문제가 있습니다.

이 문제의 경우 잘 보면

카드를 n개를 뽑았을때 이 카드를 합쳐서 모든 경우의 수를 구하라고 합니다.

이럴 때 사용하는 알고리즘이 dfs(중복순열) 입니다.

 

 

사진으로 본다면 이런식으로 가지를 뻗어 뻗어나갑니다.

각 동그라미에 있는 것들을 노드라며 하며 

 

DFS는 결국 특정 노드에서 시작해 다음 분기로 넘어가기전에 해당 분기를 완전히 탐색하는 방법입니다.

 

쉽게 말하면 , 갈 수 있는 만큼 최대한 깊이 가고 더 이상 갈 곳이 없다면 (리턴을 만나면) 이전 정점으

돌아가는 방식으로 그래프를 순회하는 방법입니다.

 

 

 

이 사진의 경우 가지수는 2개입니다 이 가지수를 결정하는 건 

dfs안에 있는 반복문으로 정합니다.

 

즉 쉽게 반복문이 3까지 반복된다면 가지수는 메서드를 만날 때 마다 반드시 3개가 뻗어나갑니다.

당연히 반복문이 4까지 반복된다면 가지수는 4로 뻗어나갑니다.

 

이러한 형태를 가지고 있는 것이 DFS입니다.

 

DFS는 여러가지 문제 에서 사용될 수 있지만

 

DFS의 대표적인 사용이유는 모든 조합론을 구할 때 사용합니다.

 

백준문제를 보며 이해를 해봅시다.

 

 

 

 

 

이러한 문제가 있습니다.

 

이 문제의 경우 657을 받앗고

 

3개의 조합을 사용해서 1 5 7 이라는 각 숫자를 이용해서

 

657보다 작고 이 숫자를 조합해서 가장 큰 숫자를 구하라는 문제입니다.

 

이 문제에서 [1,5,7]이라는 값이 있고 여기서 [5,7,7]이 3개의 조합을 이용한다면

 

657보다 작고 조합 할 수 있는 숫자 중 가장 큰 값이 됩니다.

 

즉 이 문제를 풀려고한다면 모든 조합을 찾아서 가장 큰 값을 찾아야 합니다.

 

이럴때 사용되는것이 깊이 우선탐색이라는 것이죠.

 

그림으로 본다면

 

 

이런식으로 표현될 수 있습니다.

 

즉 가지의 형식은 반복문이 몇번 돌아가냐에 따라 가지의 수가 정해집니다.

 

이 문제의 경우 3까지 반복하라 했음으로 이 재귀함수를 만날 때마다 가지가 3개씩 뻗어나가게 됩니다.

 

그렇다면 이 가지의 종료 조건은 언제까지가 되냐?

 

 

가지가 계속해서 뻗어나가다 111을 만나게 됩니다.

 

이때 또 가지가 3개로 뻗어나가면서

 

1113 1115 1117이 세 개의 값이 들어오게 됩니다.

이 경우에 입력값 657이 1113 , 1115 ,1117 보다 크기 때문에 함수 종료 메서드인 return을 넣음으로써

재귀가 종료되게 됩니다.

 

if(result > value) return;

 

 

 

 

즉 111의 가지는 3개가 뻗어나가고 여기서 리턴을 만낫기 때문에 111을 종료하고

그 옆인 113의 이동하게 됩니다.

 

마찬가지로 이 113도 3개의 가지가 뻗어나가며 657보다 큰 숫자들이 3개의 가지로 뻗어나가게 됩니다.

 

 

즉 이런식으로 또 뻗어나가고 이 세개의 가지가 뻗어 나갈때 종료조건이 657보다 크면 종료이기 떄문에

113의 값도 종료가됩니다.

 

 

즉 이런식으로 DFS는 가지 형식으로 뻗어나가며 이 메서드 기준으로 가지를 뻗고

이 가지가 리턴 함수를 만나게 되면 해당 메서드를 종료하게 됩니다.

 

즉 이 그림으로 본다면 111은 1111 , 1113 , 1115를 뻗어 나가서 리턴을 만나고

111을 종료

 

하지만 11의 메서드는

 

111 113 115 이 세개의 가지를 뻗었음으로 113 -> 115 순으로 방문하게 됩니다.

 

그렇게 세개의 가지가 검증이 끝나면 11 메서드가 뻗은 가지를 모두 검사 했음으로 

11을 종료 그렇다면 1의 가지를 봅시다.

 

1은 11 , 13 15 세 개의 가지가 존재합니다

 

 

즉 이런 형태가 되죠

 

그렇게 된다면 11의 모든 경우의 수는 검증이 끝났기 때문에 13과 15를 검증합니다.

 

그 후 13과 15를 검증을 다 하면 1의 모든 가지를 검사 했음으로 1의 메서드를 종료하고

 

3으로 넘어갑니다. 이렇게 깊이를 우선으로 계속 탐색하며 검증이 끝난다면

인근 노드들을 하나씩 검색합니다.

 

DFS를 코드로 짤 때는 주의 할 점이 있습니다.

 

1. 반복문의 갯수로 노드의 가지들이 정해진다.

 

-> 예를들어 for(int i =0; i < 3; i++ )이라 한다면 이는 현재 노드에서

3개의 가지로 뻗어나가겠다 라는 의미이다.

 

2. 재귀 함수를 사용하기 때문에 어떤 지점에서 이 재귀를 종료시킬지 정한다.

 

3. 재귀함수의 경우 return를 정의 해주어야 하며 재귀 함수의 함수 종료지점을 나타낸다.

 

이 문제의 경우 657보다 크면 의미가 없기 때문에 657보다 크면 종료를 시키게 했다.

 

 

public static void dfs(int result){

        if(result > value) return;
          max = Math.max(max, result);

        for(int i=0; i<saerch;i++) {
            dfs(result * 10 + arr[i]);
        }
}
}

 

 

코드로 본다면 이런 느낌입니다.

 

DFS경우 다른 자료구조와 섞어서 사용 할 수 있으며 

이 포스팅의 경우 DFS가 어떤느낌인지 쉽게 이해하기 위한 포스터이다.