[백준] 15649번 N과 M (1)

문제: 15649번: N과 M (1)

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

int boxs[10];
int visits[10]; // 0 번 인덱스 안써!

int n, m;

void funct(int k) {
    // 수열 출력
    if (k == m) {
        for (int i = 0; i < m; i++) {
            cout << boxs[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (visits[i] == 1) continue; // 이미 방문했으면 넘어가

        boxs[k] = i;
        visits[i] = 1; // 방문 표시
        funct(k + 1);
        visits[i] = 0; // 방문 표시 없애기
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    funct(0); // 일단 길이 0으로 시작함


    return 0;
}

 

백트래킹 문제는 처음인데 강의 내용 보니까 쉽게 이해할 수 있었다.

 

일단 백트래킹의 핵심은 각 단계마다 선택지를 골라 나아가는 것으로 생각하면 될 것 같다. 그러다가 끝에 부딪히면 이전으로 돌아가는 식인 것 같다.

 

이 문제도 같은 맥락인데 각 단계마다 선택지를 골라 나아가고 맨 끝에 부딪히면(수열의 크기가 m 의 크기와 같아지면) 현재 수열에 들어 있는 값을 출력하고 이전 단계로 돌아간다.

 

왜 재귀 다음에 백트래킹이 있는걸까 내심 궁금했는데 백트래킹 문제 풀 때 재귀를 이용해서 그런거였다. 너무 신기했다. 아무튼 재귀 문제 열심히 푼 보람이 있는 것 같다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x0C강 - 백트래킹

[실전 알고리즘] 0x0C강 - 백트래킹