순열 with DFS

0. 해당 글 작성 이유

알고리즘 문제들을 풀다보면 굉장히 다양한 푸는 방법들이 존재한다. 필자는 여기서 각 문제 마다 푸는 방식을 떠올리는 것이 중요하다는 것을 느끼고 문제 자체의 해설보다는 문제를 풀기위해 사용했던 알고리즘이나 로직들을 되새기기 위해 해당 방법들을 작성해놓을 예정이다. 이 글의 경우 프로그래머스 소수찾기 문제에서 문자열 순열 부분에서 막혔기 때문에 이 글을 작성하였다.

1. 순열이 무엇이냐

순열은 특정 수열에서 순서를 고려하여 각 수들을 선택하는 방법이다. 직관적으로 생각해보면 수들의 줄 세우기라고 생각할 수 있다. 해당 방법을 코드르 구현하는 방법은 여러가지가 있겠지만 필자는 DFS를 사용해서 구현해보고자 한다. 그리고 필자는 문자열의 순열을 구현할 예정이다.

2. DFS란 무엇이냐

DFS는 원하는 값이 나올 때 까지 탐색하여 값을 얻고 다시 되돌아가 다른 답 Case들을 연속해서 탐색하는 방법이다. 이 방법을 직관적으로 생각하면 미로에서 좌선법을 사용해서 끝까지 갔다가 막히면 바로 직전의 갈림길로 되돌아가 우선법을 하는 것이다. 해당 방법은 Vst 배열을 사용하여 재귀적으로 푸는 방법이 있다.

3. 방법

가. Set을 사용

각 문자열의 중복을 피하기 위해 Set을 사용한다.

    static Set<Integer> set;

나. DFS 중, Set에 현재 문자열 넣어버리기

void dfs(String numbers, String s, int dep) {
    if(dep==numbers.length()){
        return;
    }

    for (int i=0; i<numbers.length(); i++){
        if(!vst[i]){
            vst[i]=true;

            //여기서 그냥 넣어버림 set에 한자리 수라도
            set.add(Integer.valueOf(s+numbers.charAt(i)));
            dfs(numbers,s+numbers.charAt(i),dep+1);
            vst[i]=false;
		}
	}
}

4. 주의할 점

만약 위의 3번 "나"의 코드에서 String s에 +=을 붙여줘서 계속 초기화 시키면 재귀함수 특성상 기존 스택 메서드는 s를 계속 사용하기 때문에 s값이 바뀌면 안된다. 예를들어 "1"을 사용하고 있는데 "12"이렇게 되어버리면 백트래킹해서 다시 되돌아갈 s가 사라지기 때문에 s를 초기화 해서는 안되고 위처럼 파라미터 값으로 넘겨줘야한다.

5. 장단점

DFS를 사용해서 순열을 구하면 모든 순열의 경우를 구할 수 있다는 점과 굉장히 직관적이고 가지치기를 할 수 있다는 점들이 좋게 보이지만 O(n!)이라는 시간복잡도를 가져간다. 또한 DFS 특성상 스택을 사용하기 때문에 스택오버플로우의 위험성도 존재한다. 사용할 메모리와 시간복잡도를 판단해서 구현해야 한다. 물론 해당 방법의 다른 방법들도 존재한다. swap을 사용하여 구현하는 방법도 있다. 어떠한 방법을 선택할지는 개발자의 선택이다.

CS