문제 푼 날짜 : 2021-09-16

문제

문제 링크 : https://www.acmicpc.net/problem/15651

접근 및 풀이

이번 문제는 15649번 문제에서 자기자신을 다시 선택할 수 있어야한다는 조건이 추가되었다.
그래서 15649번 풀이에서 숫자를 선택했는지 여부를 나타내는 visited 배열과 이에 해당하는 로직을 삭제하였다.
이렇게 하면 매번 모든 숫자를 탐색할 수 있다.
설명을 좀 이해하기 힘들게 적은 것 같은데, 간단히 말해서 중복순열을 구해준 것이다.

코드

#include <iostream>

using namespace std;

int N, M;
int number[9];

void dfs(int cnt) {
    if (cnt == M) {
        for (int i = 0; i < M; i++) {
            cout << number[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= N; i++) {
        number[cnt] = i;
        dfs(cnt + 1);
    }
}

int main()
{
    cin >> N >> M;
    dfs(0);
    
    return 0;
}

결과

피드백

백트래킹에 대한 개념이 점점 잡혀가는 것 같다.