[Do it 자바 코딩테스트] 탐색 1. 깊이 우선 탐색(DFS)

1. 개념

 탐색이란 데이터를 받았을 때 원하는 데이터를 찾아내는 알고리즘이다.

깊이 우선 탐색(Depth-first-search)은 그래프 완전탐색기법 중 하나이다.  시작 노드에서 출발해 최대깊이까지 탐색하고, 끝나면 다른 노드로 이동해 다시 탐색하는 알고리즘이다.  

 

2. 핵심 원리: 재귀함수를 이용해 모든 노드를 다 돌 때까지(visited배열이 모두 true) 노드를 순회하며 전에 돌았는지 확인하고 작업을 수행한다. (main함수에서는 for문을 통해 노드의 수만큼 재귀적으로 DFS를 수행하도록 프로그래밍되어 있다.)

 

3. 예제

1)11724번

 그래프를 상상해보자. 점(node)이 n개 있고 노드를 연결하는 선(edge)이 e개 있다. 이 때 선을 따라 노드를 순회하는데 같은 노드는 한 번씩만 지날 수 있다. 이 때 연결요소의 수를 구해야 한다. 연결요소란 연결된 노드끼리 묶었을 때 그 묶음 요소를 의미한다. 

-자료구조 설정 구문

ArrayList<Integer>[] arr=> for문을 돌며 arr[i]=new ArrayList[n+1] -> 1부터 n까지의 노드 각각에 대해 연결된 노드들이 ArrayList로 있고 배열로 연결.

 

-main 함수의 로직 구문: arr의 인덱스 1~n에 대해서 기본적으로 DFS를 수행한다. 각 인덱스의 DFS가 최대로 돌아가면(재귀함수이므로)모든 노드를 다 순회할 수도 있는데, 그러면 count=1이다. 그러나 DFS(1)로 모든 노드를 다 못 돌면 두번째 DFS 사이클,DFS(2) 이 돌아가고 count=2로 올라간다. 결국 이 구문을 돌고 난 후 count의 값이 주어진 그래프의 연결요소의 수인 것이다. 

int count=0;
for(int i=1;i<=n;i++){
    if(visited[i]==false){
        count++;
        DFS(i);
    }
}

 

-DFS함수 구문: 어떤 노드에 도착했을 때 먼저 visited[v]의 값을 보고 이전에 도달한 적 없는지 확인한다. 만약 그렇다면 이 노드를 이제 방문한 것이므로 true를 저장하고, (순회하며 어떤 값을 찾고 싶다면 여기에 로직을 추가할 수 있다!) 이후 arr[v] 값을 arr의 새로운 인덱스로 보고 다시 DFS를 실행(재귀)하며 순회한다. 

public static void DFS(int v){
    if(visited[v]==true) return;
    visited[v]=true;
    for(int p: arr[v]){
        if(visited[p]==false){
            DFS(p);
        }
    }
}

 

2)2023번

 신기한 소수란, 왼쪽부터 1자리, 2자리, 끝자리까지 수를 잘라서 보더라도 다 소수인 수이다. 자릿수별로 나눠서 DFS를 수행하면 될 것이다. 재귀함수의 정의가 매우 중요하다.

DFS 수행 시, 수(int v)를 입력받고 그 자릿수(int jarisu)를 함께 입력받아야 한다 -> 소수인지 확인 후 출력+뒤에 1,3,5,7,9를 붙이고 소수이면 자릿수 하나 높인 후 DFS 추가 수행. *소수인지 확인하는 방법: 2부터 n/2까지 for문 돌며 n%i==0이면 false

public static void DFS(int v,int jarisu){
    if(jarisu==n && isPrime(v)){
        System.out.println(v);
    }
    for(int i=0;i<=4;i++){
        int j=2*i+1;
        int num=v*10+j;
        if (isPrime(num)) {
            DFS(num,jarisu+1);
        }
    }
}

 

 

-->앞의 두 예제를 통해 알게 된 것: DFS 재귀함수의 구조는

(1)입력값으로 받은 int v(작업하는 대상 노드)에 대해 필요한 작업을 수행하기 -> 노드한번만 지나도록 / 소수인지 확인 후 출력

(2)그 다음에 DFS를 수행할 대상 노드를 정해 DFS 시킨다. ->v를 인덱스로 하는 리스트 순회해 DFS / 13579붙이고 소수면 DFS

 

3)13023번

1)의 문제와 입력값이 유사하다. n개의 노드와 e개의 엣지가 주어지므로 그래프를 ArrayList<Integer>[] arr형태로 나타낼 수 있다.

1)에서는 로직이 여러 DFS 연결요소를 순차적으로 돌 때 겹치는 노드가 연결요소 간에 없어야 했다->백트래킹 이용X, 연결요소들을 돌아도  static visited 배열 유지, true 누적. 

2)에서는 로직이 가능한 모든 DFS 연결요소들을 돌면서 길이가 5 이상인 연결요소의 존재를 알아내면 된다->백트래킹 이용O, 하나의 DFS loop(연결요소) 내에서만 visited를 누적시켜야 한다.(가능한 모든 연결요소 경우 고려해야 함+DFS가 무한루프 돌면 안됨)

또한 길이를 추적하다가 5가 되면 DFS루프를 즉시 종료해야 한다 -> 노드번호 v에다가 depth인자도 추가!

 

-main함수의 로직(자료구조 설정 후): 깊이 1에서 모든 노드를 시작노드로 해 탐색해본다. 

for(int i=0;i<n;i++){
    DFS(i,1);
}

 

-DFS함수의 로직

(1)로직 수행 부분: DFS함수가 시작하자마자 depth가 5인지 검사해 true라면 즉시 리턴한다.

(2)DFS 재귀함수 부분: 백트래킹로직 적용(재귀부분를 visited[v]=true, false구문으로 닫는다) + v값을 arr의 인덱스로 해 요소 순회(depth+1해서 재귀한다)

public static void DFS(int v,int depth) {
    //1. 로직 수행(바로 문제에서 필요하다는 거 수행)
    if(depth==5){
        result=1;
        return;
    }
    //2. 다음 DFS 수행
    visited[v]=true;     //하나의 연결요소를 다 순회하기 시작할 때 지나간 노드에는 true설정.
    for(int i:arr[v]){
        if(visited[i]==false){
            DFS(i,depth+1);   //그 연결요소 내에서 가지를 치고, 안 지나간 노드는 깊이를 1씩 더하며 DFS한다.
        }
    }

    visited[v]=false;     //하나의 연결요소 다 순회해서 내부의 DFS들이 깊은 것부터 하나씩 종료되고 가장 얕은 것까지 와, for문이 끝나면 지나간 노드들을 모두 false설정.
}

 

 

-->알게 된 것

DFS의 구성: 함수의 핵심로직(DFS써서 얻고자 하는 것) + 재귀함수 적용로직(백트래킹 선택, 깊이 1씩 더하며 DFS 재귀가능)

DFS의 의미: 깊이를 더하면서 재귀함수 실행한다는 점과 그것을 실제 문제에서 적용하기 위해 백트래킹을 사용한다는 점이 DFS가 재귀함수에 속하지만 그것만이 가지는 차별점이라고 생각한다.

 

재귀함수가 점화식 세우는 느낌이라 그 노드에 대해 해야하는 로직과 다음 노드로 넘어가기 위한 로직이 함께 존재한다는 느낌인데, 식을 세우고 수학문제 푸는 느낌이라 재밌는 것 같다. 재귀함수 문제를 DFS 이외에도 더 폭넓게 풀어보고 더 익숙해지고 싶다.