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

- 백준 온라인 저지의 15649번 문제입니다.

 

- 문제 분류는 [백트래킹]으로 분류되어 있습니다.

 

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

15649번: N과 M (1)

 

- 백트래킹 분류의 문제를 처음 업로드하므로, 백트래킹에 대한 개념을 잠깐 언급하겠습니다.

 

- 구글에 백트래킹이라는 단어를 검색하면, 1950년대 어떤 수학자가 고안해낸 '전략'이라고 합니다.

 

- 하지만 우리에겐 이런건 별로 도움이 되지 않습니다.

 

- 간단하게 생각하면, DFS(깊이우선탐색) 알고리즘에서, 정답이 아닌 곳은 애초에 '배제' 하는 전략입니다.

 

- 많은 사람들이 백준 9663번 N-Queen 문제로 이 개념을 설명합니다.

 

- 그러므로, 다른 분들이 설명한 N-Queen 문제를 보시면 됩니다........(저는 추후에 업로드 예정입니다.)

 

- 이 문제를 저는 DFS로 풀었습니다.

 

- 그럼 백트래킹을 하지 않은 것이 아니냐? 하는 분들도 계실겁니다..

 

- 맞는 말입니다..

 

문제

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

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

입력

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

출력

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

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

 

풀이

- 우선 저는 처음에 아래와 같이, 문자열로 변환 후

 

- next_permutation과 substr을 활용하여 풀어보려고 했습니다.

 

- 시간초과입니다.

 

- 이유는 간단합니다. 

 

- 예를 들어 4 개중 2개 뽑기의 해 중에서 [1 2]가 나올 경우를 생각하면,

 

- next_permutation은 [1 2]를 찾기 위해 [1 2 3 4] [1 2 4 3] 두개 다 검색합니다.

 

- 매우 비효율적입니다.;

 

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
	int n, m;

	cin >> n;
	cin >> m;

	string str = "";
	for (int i = 1; i <= n; i++)
	{
		str += to_string(i);
	}

	int result = true;
	set<string> s;

	while (result)
	{
		s.insert(str.substr(0, m));
		result = next_permutation(str.begin(), str.end());
	}

	set<string>::iterator it;
	string temp;
	for (it = s.begin(); it != s.end(); it++)
	{
		temp = *it;

		for (int i = 0; i < temp.length(); i++)
		{
			cout << temp[i] << " ";
		}

		cout << endl;
	}

	return 0;
}

 

 

- 다음은 DFS입니다.

 

- next_permutation을 활용할 때 보다 가지수가 적습니다.

 

- 이유는, 종료 조건을 통해 일정 깊이 이상 들어가지 않기 때문입니다.

 

- 4개중 2개 뽑으면 깊이2까지밖에 안들어가므로,

 

- next_permutation사용할때 처럼 [1 2 3 4] [1 2 4 3]을 다 보지 않아도 되기 때문입니다.

#include <iostream>

using namespace std;

#define MAX 8
int N,M;

int store[MAX];
int visit[MAX+1];

void dfs(int phase)
{
    // 종료조건
    if(phase == M)
    {
        for(int i=0;i<M;i++)
        {
            cout << store[i] << " ";
        }
        cout << "\n";
        return;
    }
    
    for(int i=1;i<=N;i++)
    {
        if(visit[i] == false)
        {
            visit[i] = true;
            store[phase] = i;
            dfs(phase+1);
            visit[i] = false;
        }
    }
}

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