코딩 테스트를 위한 알고리즘 - DFS를 통한 순열, 조합 구현

진행 동기

요즘 저는 취업을 위해 코딩 테스트 문제를 풀고 있습니다.

코딩 테스트에 나오는 문제 중에서 DFS를 통한 순열, 조합을 이용해서 풀어야 하는 것들이 자주 나오는 거 같아서 이번에는 DFS 개념과 이를 이용한 순열, 조합 구현에 대해 포스팅을 작성해 보려고 합니다.

 

DFS

DFS(Depth-first search)란 깊이 우선 탐색으로 그래프 자료구조의 모든 정점을 깊이를 우선하여 탐색하는 검색 알고리즘 입니다.

 

https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

탐색하는 방식은 위 그림과 같습니다.

 

코딩 테스트에서 DFS 알고리즘은 "백트래킹(backtracking)" 을 위해 사용됩니다.

 

백트래킹(backtracking)

기본 개념은 DFS 이지만, 현재 있는 위치에서 조건에 부합하는 모든 경로를 탐색하고, 일정 깊이에 도달하거나 조건에 부합하지 않는 순간 뒤로 돌아가서(백트래킹) 다른 경로를 탐색하는 것이 가장 큰 특징입니다.

 

"가능한 모든 경로"를 "재귀적으로 탐색"한다는 것이 핵심적인 개념입니다.

 

이 개념을 통해 순열, 조합을 구현해 볼 것입니다.

 

순열

순열은 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 것입니다.

 

코드를 우선 보여드리겠습니다.

import java.util.*;

public class Main {
    static int[] ch,arr;
    Stack<Integer> pm = new Stack<>();
    static int n, r;

    void DFS(int L) {
        if (L == r) {
            for(int x : pm) System.out.print(x + " ");
            System.out.println();
        }else {
            for (int i = 1; i < n; i++) {
                if(ch[i] == 0){
                    ch[i] = 1;
                    pm.push(i);
                    DFS(L + 1);
                    pm.pop();
                    ch[i] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        r =kb.nextInt();
        arr=new int[n];
        for(int i=0; i<n; i++) arr[i]=kb.nextInt();
        ch=new int[n];
        T.DFS(0);
    }
}

 

• L == r : r개를 선택하는 것이므로 깊이가 r에 도달하면 현재 경로 탐색 중지
• ch[i] == 0 : 중복없이 선택해야 하므로 현재 선택되어 있는 숫자로는 탐색 X
• DFS(L+1) : 조건에 부합하면 숫자를 선택했다는 의미이므로 L+1을 전달

DFS 함수를 호출하는 순간이 탐색을 위한 가지를 뻗는 것을 의미하고 그 아래 코드는 백트래킹을 위해

그 전 상태로 돌아가기 위함을 나타냅니다.

 

코드를 구체적으로 이해하기 전에 해당 코드가 어떤 의미 혹은 역할을 하는지 이해하는 것이 중요합니다.

그래서 제가 설명한 백트래킹의 핵심 개념을 의미하는 코드를 빨간 네모 박스와 함께 설명을 달아 두었습니다.

 

조합

조합은 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관없게 선택하는 것입니다.

 

import java.util.*;
class Main {
    static int n, r;
    Stack<Integer> combi = new Stack<>();
    public void DFS(int L, int s){
        if(L== r){
            for(int x : combi) System.out.print(x+" ");
            System.out.println();
        }
        else{
            for(int i=s; i<=n; i++){
                combi.push(i);
                DFS(L+1, i+1);
                combi.pop();
            }
        }
    }
    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        r =kb.nextInt();
        T.DFS(0, 1);
    }
}

• L  == m : r개 선택 후 현재 경로 탐색 중지
• DFS(L+1,i+1) : 현재 선택한 r의 개수와 중복 선택을 없애기 위해 순열과 다르게 매개변수 추가

코드로 이해하기 보다는 그림을 그려서 이해하시는 걸 추천 드립니다.

DFS가 노드를 그려넣어야 하는 타이밍임을 알게되면 그림 그리기도 한결 더 쉬워질거라고 생각합니다.

 

---

이번 포스팅에서는 DFS의 개념과 이를 이용한 백트래킹에 대해 알아보았습니다. 현재 코딩 테스트에서 백트래킹을 적용한 문제가 자주 나오는 것 같아서 백트래킹 개념을 적용한 순열,조합에 대해서도 공부해 보았습니다.