• 백준 6603번 로또 :: 마이구미
    알고리즘 풀이/그래프 2017. 8. 1. 21:24
    반응형

    이번 글은 백준 알고리즘 문제 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


    6603번 로또


    가장 처음 고를 수 있는 경우는 {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;)

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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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;
    }
    cs


    반응형

    댓글 3

    • Favicon of https://mygumi.tistory.com mygumi 2019.09.17 22:59 신고

      임경호 - 전체코드를 볼 수 있을까요???ㅜㅜ
      => Github 참고 바랍니다~
      https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/6603.java

    • Favicon of https://mygumi.tistory.com mygumi 2019.09.17 23:00 신고

      백지은 - 안녕하세요 열심히 잘보고 있습니다.
      for (int i = 0; i < k; i++) {
      cnt = 1;
      dfs(i, array[i] + " ";);
      }
      여기서 잘 모르겠는게 있는데요,dfs에 i가 들어가는건, 만드는 배열 중 가장 작은게 i번째 숫자 즉0번째 숫자가 들어가는 조건에서 5개를 뽑고, 그다음엔 0번째 숫자는 안뽑고 1번째 숫자가 들어가는 조건하에서 5개를 뽑고 이렇게 가는 것같은데요, 그러면 k까지 가는게 아니라 S-k까지 가야 하는 것 아닌가요?
      => 네 맞습니다. 말씀하신대로 조건이 i < k - 5 가 되는 것이 맞습니다.
      저같은 경우는 DFS 쪽에서 사이즈가 6일때만 성립하는 조건이 있어서, 신경쓰지 않았지만.... ㅎㅎ
      혼란이 올 수 있겠네요.. 수정하겠습니다.
      생각하신 부분이 맞습니다! 읽어주셔서 감사합니다~

    • Favicon of https://mygumi.tistory.com mygumi 2019.09.17 23:01 신고

      Park Seokjun - 저는 처음에 DFS 함수가 cnt 매개변수를 갖고 있는 방법으로 구현하였는데요. 그런데 올려주신 것처럼 cnt를 들고 있지 않는 경우가 back tracking을 직관적으로 표현하는 것 같아서 만들어보니 cnt 증감이 조금 헷갈리네요...코드르 보면 DFS 함수 내에 for문을 한 번 돌 경우 재귀 호출로 인해 DFS(v+1)가 호출 될것이고 이 때 cnt는 +1, 그리고 두 번 돌 때에는 DFS(v + 2)가 또 호출되고 cnt는 +2 이런식으로 진행이 되는 것인가요? 하나의 for문에서 호출된 여러 DFS 함수들은 모두 같은 cnt값을 갖고 있어야 될 것 같은데...답은 제대로 나오니 혼란스럽습니당
      => cnt 를 전역으로 두어, 직관적으로 느끼실 수도 있겠네요...
      하지만 혼란스러우신건 위 코드가 어떻게 동작하는 지에 대해 아직 확실히 이해하지 못하신것 같습니다..
      글에서 표현한 그림을 그대로 코드로 구현한 형태인데 DFS 이기 때문에 가능합니다.
      DFS는 깊이 탐색으로써, BFS 처럼 하나의 정점에 연결된 정점들을 다 거치는 것이 아닌 타고타고 들어갈 수 있을 때까지 들어가는 로직입니다.
      현재 코드의 dfs 가 어떻게 동작하는지 그려보시면서 cnt 의 상태를 추적하시면 이해하실 수 있을 거라 생각합니다!
      읽어주셔서 감사합니다!

Designed by Tistory.