문제 푼 날짜 : 2021-09-15

문제

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

접근 및 풀이

재귀적으로 순열을 구현하면되는 문제였다. https://yabmoons.tistory.com/100?category=838490 이 곳에 아주 설명이 잘되어있어 도움이 많이 되었다.
dfs를 이용하여 몇 개의 숫자가 선택되었는지 확인해주다가, 숫자가 M개가 선택되었을 때 선택된 숫자들을 출력해준다.(가지치기)
선택된 숫자는 int 배열(코드 내의 number)에 저장해주었고, 숫자들의 선택 유무를 알기 위해 bool 배열(코드 내의 visited)을 선언해 주었다.

+) cout << end; 을 쓰지말자... 너무 느리다... 왜 시간초과가 났는지 몰랐는데, 이것 때문에 계속 시간초과가 났다...

코드

#include <iostream>

using namespace std;

int N, M;
int number[9] = { 0, };
bool visited[9] = { false, };

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++) {
        if (visited[i] == false) {
            visited[i] = true;
            number[cnt] = i;
            dfs(cnt + 1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> N >> M;

    dfs(0);
    return 0;
}

결과

피드백

백트래킹 문제를 아직 제대로 못 푸는 것 같다. 좀 더 많은 문제를 풀어보고 익숙해져야겠다.