백준 6603번 로또 :: 마이구미

이번 글은 백준 알고리즘 문제 6603번 "로또" 를 다뤄본다.

문제를 보다시피, 모든 경우의 수를 찾아야한다.

DFS에서 백트래킹을 응용하여 문제를 해결할 수 있다.

이 문제의 코드를 이해한다면, 재귀 함수와 친해질 수 있을 것이다.

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

독일 로또는 {1, 2, ..., 49}에서 숫자 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 숫자 중 k(k>6)개의 숫자를 골라 집합 S를 만든 다음 그 숫자만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 숫자를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 숫자를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

예제를 보다시피, 고를 수 있는 모든 경우를 오름차순으로 출력하는 것을 볼 수 있다.

문제 접근은 보이는 그대로 생각하면 된다.

DFS를 통해 깊이 탐색한 후, 6개를 고르면 백트래킹을 통해 고르지 않은 다음 번호를 고르면 된다.

그림으로 표현하면 아래와 같다.

input - 1, 2, 3, 5, 8, 9, 10

가장 처음 고를 수 있는 경우는 {1, 2, 3, 5, 8, 9} 이 된다.

다음은 9에서 백트래킹 후 10을 방문하면 {1, 2, 3, 5, 8, 10} 을 고를 수 있다.

그 다음은 8에서 백트래킹 후 9를 방문할 수 있다. {1, 2, 3, 5, 9, 10}

for (int i = 0; i < k - 5; i++) {
    cnt = 1;
    dfs(i, array[i] + " ");
}

public static void dfs(int v, String str) {
    if (cnt == 6) {
        sb.append(str + "\n");
    } else {
        for (int i = v + 1; i < k; i++) {
            ++cnt;
            dfs(i, str + array[i] + " ");
        }
    }
    --cnt; // backtracking
}

방문 여부에 대한 visited 같은 배열이 사실 상 필요없다.

오름차순 되어있는 번호를 탐색할 때마다 보다 큰 수를 탐색하기 때문이다. (int i = v + 1;)

펜을 들고 직접 그려보면 이해를 할 수 있다.

private void solve() {
    while ((k = sc.nextInt()) != 0) {
        array = new int[13];
 
        for (int i = 0; i < k; i++) {
            array[i] = sc.nextInt();
        }
 
        for (int i = 0; i < k; i++) {
            cnt = 1;
            dfs(i, array[i] + " ");
        }
 
        sb.append("\n");
    }
    System.out.println(sb.toString());
}
 
public static void dfs(int v, String str) {
    if (cnt == 6) {
        sb.append(str + "\n");
    } else {
        for (int i = v + 1; i < k; i++) {
            ++cnt;
            dfs(i, str + array[i] + " ");
        }
    }
    --cnt;
}