[88] C++(Cpp) 백준 15649번: N과 M(1) 문제 (백트래킹)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3 복사

4 4

예제 출력 3 복사

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

 

 

 

 

<풀이>

https://dlog0518.tistory.com/54

BOJ-백준 15649번 N과 M(1) C++

https://velog.io/@mmindoong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9BackTracking

[알고리즘] 백트래킹(BackTracking)

위 블로그의 풀이를 참고하였음.

 

https://hwan-shell.tistory.com/119

C++ vector사용법 및 설명 (장&단점)

vector에 대해서 정리한 블로그.

 

 

이 문제는 백트래킹을 이용하여 푸는 문제이다. 

백트래킹이란 해를 찾으로 돌아다니는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.

대표적인 완전 탐색 방법으로 DFS(Depth First Search, 깊이 우선탐색)이 있는데, 이 방법은 현재 지점에서 방문할 곳이 있으면 '재귀 호출'을 이용해서 계속 이동한다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다. https://chanhuiseok.github.io/posts/algo-23/ 출처

 

void dfs(int cnt){
    if (cnt == M){ //깊이(길이)가 M과 같다면 수열 출력
        for (int i = 0; i < vec.size(); i++){
            cout << vec[i] << ' ';
        }
        cout << '\n';
        return ;
    }

    for (int i = 1; i <= N; i++){
        if (visited[i]) continue; // 이미 방문한 숫자라면 건너뛰기
        visited[i] = true; //이미 방문하지 않았을 경우
        vec.push_back(i); 
        dfs(cnt + 1);  // 깊이 + 1 해서 재귀
        vec.pop_back(); // 수열 출력 후 끝 수 삭제 및 false 후 for문 돌며 반복
        visited[i] = false;
    }
}

dfs 함수는 cnt(깊이)를 매개변수로 받아 입력받은 M과 같아지면 수열을 출력하게 한다.

 

1부터 N까지 숫자를 탐색하는 for문을 작성한다.

- for 문의 i가 true라면 이미 방문했으므로 건너 뛴다.

 - for문의 i가 아직 방문하지 않은 숫자라면 bool형 배열인 visited[]에 방문 체크를 해준다.

 - 수열을 저장하는 vector에 i를 넣어준다.

 - dfs(cnt+1)을 넣어 새로운 dfs를 수행한다.

 - 위 과정을 반복하다가 cnt == M이 된다면 vector에 저장되어 있는 수열을 출력한다.

 - 뒤에 실행 된 dfs함수부터 차례대로 pop_back()을 해주어 수열을 비워주고 visited[]를 false로 갱신하며 되돌아간다.

 - 차례로 돌아온 i 부터 다시 for문이 돌며 위의 과정을 반복한다.

 

 

맞는지는 모르겠지만 대충 그려본 과정 N=3, M=2일 때

 

<제출한 코드>

#include <iostream>
#include <vector>
#define MAX 9
using namespace std;

int N, M;
bool visited[MAX] = {0, }; // 중복 방문 방지
vector<int> vec; // 수열 출력을 위해

void dfs(int cnt){
    if (cnt == M){ //깊이(길이)가 M과 같다면 수열 출력
        for (int i = 0; i < vec.size(); i++){
            cout << vec[i] << ' ';
        }
        cout << '\n';
        return ;
    }

    for (int i = 1; i <= N; i++){
        if (visited[i]) continue; // 이미 방문한 숫자라면 건너뛰기
        visited[i] = true; //이미 방문하지 않았을 경우
        vec.push_back(i); 
        dfs(cnt + 1);  // 깊이 + 1 해서 재귀
        vec.pop_back(); // 수열 출력 후 끝 수 삭제 및 false 후 for문 돌며 반복
        visited[i] = false;
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    dfs(0);
    
    return 0;
}