[C언어] 백준 15651 : N과 M (3)

먼저 나는 N과 M (3)을 진행했는데, 이유는 이게 제일 1~4중에서 쉬워보였기 때문이다.
조건없이 출력만 하면 되기에 이거를 먼저 잡고가야겠다고 생각했다.

n값과 m값을 입력받을 때에 어떻게 진행해야 되는지 몰랐다.
또한 백트래킹이 무엇인지 몰랐다. 그래서 구글링을 했다. 어떻게 출력하는지 알면, 나머지 1,2,4번도 예외처리만 하면 될 것 같아서 답을 보고 이해하는방식으로 진행했다.

답 이해한 뒤, 혼자 다시 푼 코드

#include <stdio.h>

int arr[7] = {0, };

void BT(int n, int m, int d)
{
    int i, k;
    i = 1;
    while(i <= n)
    {
        arr[d] = i; // 이 값은 기준값이 된다.
        if (m - 1 == d) // m이 1씩 커질수록, BT를 한번씩 더 호출한다.
        {
            k = 0;
            while(k < m) // k는 배열을 출력한다. 그러기에 0부터 시작한다.
            {
                printf("%d ", arr[k]);
                k++;
            }
            printf("\n");
        }
        else
        {
            BT(n, m, d + 1);
        }
        i++;
    }
}

int main()
{
    int n,m;
    scanf("%d %d", &n, &m);
    BT(n, m, 0);
}

설명

1. 쉽게 예를 들어보자. n = 3, m = 2 이라고 하면, 출력이 1 1 / 1 2/ 1 3 / 2 1/ 2 2/ 2 3/ 3 1/ 3 2/ 3 3 이렇게 된다.

2. BT에 3, 2, 0이 들어간다. 반복문으로 들어간다. arr[0] = 1. BT로 재귀.

3. 반복문 들어간다. arr[1] = 1, 2(m) - 1 == 1(d) 이기에 if에 걸린다.

4. k로 arr[0], arr[1]을 출력한 뒤 엔터. 여기까지 1 1/를 출력했다.

5. i++로 증가해서 arr[1] == 2가 되었고, 다시 k로 arr[0],arr[1]를 출력해서 1 2/를 출력한다. 반복하면 1 4/ 까지 출력된다. 그리고 BT가 끝나면서 2번에서 호출한 재귀가 끝난다.

6. i++로 arr[0] = 2가 된 뒤, 다시 BT를 호출한다.

7. arr[1] = 1이고, 다시 k로 2 1/를 출력하고 위 3번 ~ 5번과정을 반복하면 2 4/까지 된다.

8. BT가 또 다시 끝났다. 6 ~ 7번과정을 반복한다.

9. 끝.

https://typoon.tistory.com/8 여기에서 도움을 받았다. 그냥 같은 코드라고 봐도 무방하다.