[완전 탐색] 백준 문제 풀이 - 15649 N과 M (1)

👩🏻‍💻 문제링크

 

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

15649번: N과 M (1)

 

✍️ 아이디어

 

못풀었다...재귀 자체가 생각이 안남

 

✍️소스코드

 

#include <iostream>
using namespace std;
bool c[10]; // 이미 방문한 숫자인지 체크함(백트래킹)
int a[10]; // 숫자 저장용
void dfs(int index, int n, int m)// 로직 자체가 dfs임
{
    if (index == m) // 저장이 다 이루어지면 출력해야지
    {
        for (int i=0; i<m; i++) {
            cout << a[i];
            if (i != m-1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i=1; i<=n; i++) 
    {
        if (c[i]) continue; // 한번 방문한 숫자면 건너뜀(중복 방지)
        c[i] = true; // 숫자에 방문 했다는것을 저장
        a[index] = i; //index 번째에 수를 저장
        go(index+1, n, m); // index에 1 더함(다음 자리에 숫자 저장)
        c[i] = false; // 4,3,2,1 순으로 false로 바뀜 => 3 false 되면 1243 출력
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    dfs(0,n,m);
    return 0;
}

 

 

체감난이도	걸린시간	참고	사용 문법
??	1hour	강의 및 블로그	DFS, 재귀, 백트래킹