DFS로 조합구하기

알고리즘

DFS로 조합구하기

제이G 2022. 12. 30. 18:17

Remember

해당 포스팅은 https://www.acmicpc.net/problem/17471 문제를 풀며, 조합을 구하는 과정에 시간 소요가 많이 되어 다시 한번 dfs로 조합을 구하는 방법에 대해 정리하고자 한 글이다. 이 외의 문제들 중에서도, 조합 + @를 요구하는 문제가 빈번히 나오기 때문에 조합을 구하는 구현부분에서 시간이 막히면 안되고 이를 개선하고자 글을 작성하고자 한다.

dfs 설계

dfs 재귀 탐색은 기본적으로 트리 자료구조를 재귀적으로 방문하는 논리적인 구조를 갖고 있기 때문에 설계 단계에서 가상의 트리 (State-Space Tree. 이하 SST)를 작성하여 접근한다면, 구현 실수를 미연에 방지할 수 있다.

SST 설계

ex) [1, 2, 3, 4]의 nCr 조합을 구하시오.

메소드 시그니쳐가 dfs( int depth, int idx ) 라고 해보자.

연결된 곳은 어디인가?
1 ~ N
갈 수 있는 곳은 어디인가? (SST의 "X" 지점을 파악하면 알 수 있다.)
현재 idx + 1

이를 코드로 한 번에 나타내면 다음과 같다.

dfs (int depth, int idx) {
...
    for(int num=idx+1 ~ N) {
        ...
    }
...
}

depth의 논리적인 의미를 살펴보자.

재귀 탐색하며 구하는 조합을 리스트 혹은 배열에 기록한다고 했을 때, depth는 기록하고자 하는 리스트 / 배열의 인덱스임을 알 수 있다. 또한, depth+1 은 nCr 의 "r"을 의미함을 알 수 있다. (n개 중 r개를 뽑는 것이므로)

즉, depth는

리스트 / 배열의 인덱스
depth +1: nCr의 "r"

여기에 더 나아가, 체크인(방문 시 해야하는 행동)에 대해 고려해보자.

방문 시, 우리는 리스트/ 배열의 depth 번째 인덱스에 기록을 해야하므로, 코드는 아래와 같다.

dfs (int depth, int idx) {
// 체크인:
    combiArr[depth] = idx;
    or
    combiList.add(depth, idx);
...
}

이제 체크아웃(재귀 탈출 직전 해야하는 행동)에 대해 고려해보자.

dfs (int depth, int idx) {
...
//체크아웃:
    combiArr[depth] = 0;
    or
    combiList.remove(depth);
}

물론, 배열의 경우 depth번째 인덱스에 "덮어쓰기"를 해주므로 해당 과정을 생략해도 된다.

이 경우는 base case (Leaf Node)에 대한 고려해도 괜찮을 경우에만 해당한다. (리프 노드에 도달 시, 그 과정에서 모든 idx의 값들이 덮어쓰기되어 조합이 도출되기 때문)

하지만, nCr의 조합을 구하는 과정 (방문하는 모든 노드들)에 대한 고려를 해야할 경우, 위의 체크아웃 구현을 해주어야 한다.

수도 코드

[ 체크인을 dfs 메소드 콜 직후에 하는 경우 ]

dfs (int depth, int idx) {
// 1. 체크인: depth 번째 idx에 기록
	combiList.add(depth, idx);

// 2. base case:  n 개중 r개를 뽑아라. 즉, r개를 다 뽑은 경우
    if (depth == R - 1) {	// depth 1지점을 depth 0으로 시작했음을 기억
        
    } else {

// 3. 연결된 곳 + 갈 수 있는가?
        for (int num=idx+1 ~ N) {
            dfs (depth + 1, num);
        }
    }

// 4. 체크아웃: depth 번째 idx의 원소 삭제
	combiList.remove(depth);
}

[ 체크인을 dfs 메소드 콜 후 for문에서 하는 경우 ]

dfs (int depth, int idx) {

// 1. base case:  n 개중 r개를 뽑아라. 즉, r개를 다 뽑은 경우
    if (depth == R) {	// 체크인의 위치와 재귀 콜 구조를 생각해본다면 R-1 -> R로 바꿔야 함
        return;
    }

// 2. 연결된 곳 + 갈 수 있는가?
    for (int num=idx+1 ~ N) {
        // 3. 체크인: depth 번째 idx에 기록
	    combiList.add(depth, idx);
        
        dfs (depth + 1, num);
        
        // 4. 체크아웃: depth 번째 idx의 원소 삭제
        combiList.remove(depth);
    }
}

두 방법의 구현의 차이가 조금 있음을 주목하자.

첫 번째 방법: "방문 했을 때" 리프노드(base case)에 도착했는지 판단
방문을 해서 체크인을 했고, 리프노드이기 때문에 다시 돌아가야 한다. 이미 체크인을 했기 때문에 체크아웃도 이루어져야 하므로, 바로 return을 하면 해당 depth의 탐색에 대한 체크아웃을 수행하지 못하게 된다. 따라서, else 분기문으로 코드를 작성해야 한다.
두 번째 방법: 리프노드(base case)에서 한번 더 방문했을 때 판단
한번 더 방문한 경우이기에 별도의 체크아웃 없이 바로 return하면 된다.

코드

public class Dfs조합구하기 {
	static int N, R;
	static List<Integer> combiList = new ArrayList<Integer>();
	static int[] combiArr;

	public static void main(String[] args) {
		N = 5;
		R = 4;
		combiArr = new int[N];
//		nCombiR_Ver1(-1, 0);
		nCombiR_Ver2(0, 0);
	}

	private static void nCombiR_Ver1(int depth, int idx) {

		// check-in:
		if (depth != -1) {
			combiList.add(depth, idx);
		}

		// base case: n 개중 r(depth)개를 뽑아라. 즉, r개를 뽑은 경우
		if (depth == R - 1) {
		} else {
			// recursive case:
			// 연결된 곳 + 갈 수 있는가?
			for (int num = idx + 1; num <= N; num++) {
				nCombiR_Ver1(depth + 1, num);
			}
		}

		// check-out:
		if (depth != -1) {
			combiList.remove(depth);
		}
	}

	private static void nCombiR_Ver2(int depth, int idx) {

		// base case:
		if (depth == R) {
			return;
		}

		// recursive case:
		for (int num = idx + 1; num <= N; num++) {
			// check-in:
			combiList.add(depth, num);
			// 간다
			nCombiR_Ver2(depth + 1, num);
			// check-out:
			combiList.remove(depth);
		}
	}
}