[백준/C] 6603 - 로또

https://www.acmicpc.net/problem/6603

---

DFS (Depth-First Search)

dp를 이용할까 하다가, 찾아보니까 dfs로 푸는 것이 더 간단해 보여서 푸는 김에 공부해보기로!

DFS에서는 가능한 한 깊은 노드를 탐색하다가, 더 이상 탐색할 노드가 없으면 이전 분기점으로 돌아가 다른 경로를 탐색한다.

쉽게 이해하려면 아래와 같은 예시를 생각해보면 된다.
ex. 미로에서 길을 찾는 경우, 길이 막히면 마지막 갈림길로 돌아가 다른 방향으로 간다. 이렇게 길을 찾을 때까지 계속 시도한다.

dfs는 조합이나 순열 관련 문제를 풀 때 유용하다고 한다.

DFS 함수

DFS 함수는 재귀함수이다. 일반적인 DFS 함수의 구성은 아래와 같다.

1. 각 노드의 방문 여부 기록
2. 재귀 호출 - 현재 노드에서 이동할 수 있는 각각의 이웃 노드에 대해 재귀적으로 호출 (이 과정이 아까 미로를 예시로 든 경우의 '갈림길' 처리와 비슷하다고 보면 된다.)
3. 종료 조건

---

해결 과정

문제를 요약해보자면, 주어진 k개의 수로 만들 수 있는 6개 수의 모든 조합을 출력하면 된다.

배열을 사용한 DFS 함수

참고
파라미터로는 start, depth 를 준다.

1. depth == 6 이라면 6개의 숫자를 모두 뽑은 것이므로 현재 배열에 담아 놓은 요소를 모두 출력, 줄바꿈 이후 return; 해준다.
2. depth != 6 이라면
   1) current 배열에 입력받은 숫자들 중 i번째 요소 저장해주기
   2) i + 1, depth + 1 을 전달해 주면서 재귀호출

문제점

처음에 main 함수 내에서 while문을 안 쓰고 구현하려고 했었는데, dfs 함수에 잘못된 부분이 없는데도 자꾸 오류가 떠서 그냥 전체를 while문 안에 넣었더니 성공했다.

while문 안에서 scanf() 사용하기

이 문제에서처럼 받은 입력에 따라 반복을 계속할지 결정할 때 while문 안에 scanf()를 넣어서 사용하면 코드가 깔끔해진다.

while (scanf("%d", &k), k != 0) {
    printf("입력받은 값: %d\n", k);
    // 추가적인 작업
}

이렇게 코드를 작성하면, 루프에서 scanf()로 k값을 읽은 후, k값이 0이 아닌 경우에만 계속 실행되게 된다. k가 0이라면 루프가 종료된다. 따라서 while문 안에서 if (k == 0) break; 이런 걸 써줄 필요가 없게 된다!

---

전체 코드

#include <stdio.h>
#include <stdlib.h>

void dfs(int start, int depth, int k, int current[], int nums[]) {
    if (depth == 6) {
        for (int i = 0; i < 6; i++) {
            printf("%d ", current[i]);
        }
        printf("\n");
        return;
    }
    for (int i = start; i < k; i++) {
        current[depth] = nums[i];
        dfs(i + 1, depth + 1, k, current, nums);
    }
}

int main() {
    int k;
    int isFirst = 1;

    while (scanf("%d", &k), k != 0) {
        if (!isFirst)
            printf("\n");
        else
            isFirst = 0;
        
        int *current = (int *)malloc(sizeof(int) * 6);
        int *nums = (int *)malloc(sizeof(int) * k);
        for (int i = 0; i < k; i++)
            scanf("%d", &nums[i]);

        dfs(0, 0, k, current, nums);
        free(current);
        free(nums);
    }
    return 0;
}