[백준/C++] 15663 N과 M(9) (S2)

유형	난이도	완료일	링크	특이사항
백트래킹	실버2	23/03/31	https://www.acmicpc.net/problem/15663

 

 

내 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[10001];
int n, m;

vector <int> box;

void DFS(int idx, int depth)
{
	
	if(depth > m)
	{
		for(int a: box)
			cout<< a << " ";
		cout<<"\\n";
		return;
	}

		
	for(int i= 0; i<10001; i++)
	{
		if(arr[i]==0)
			continue;
		
		arr[i]--;
		
		box.push_back(i);
		
		DFS(i,depth+1);	
		
		box.pop_back();
		
		arr[i]++;
	}
}

int main(void)
{
	cin >> n >> m;
	
	int k;
	for(int i=0; i<n; i++)
	{
		cin >> k;
		arr[k]++;
	}	
	
	
	DFS(0,1);
}

  이전 문제들과 달리 입력으로 중복된 수가 주어질 수 있는 문제다. 따라서 숫자들을 입력 받아 배열에 저장하는 방식이 아닌 숫자 범위인 10000까지를 인덱스로 갖는 배열을 만들어 숫자가 입력될 때마다 그 값에 +1 하는 것으로 대체하였다. 값이 0이 아닌 곳을 방문하고 방문한 곳은 값 -1 을 한다. 여러번 입력 받은 숫자가 그만큼 출력될 수 있게 하였다.

다른 코드

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

bool check[9];
int num[9], ans[9];
int N, M;

void dfs(int x, int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < M; i++)
			cout << ans[i] << " ";
		cout << '\\n';
		return;
	}
	int tmp= -1;
	for (int i = 0; i < N; i++)
	{
		if (!check[i] && tmp != num[i])
		{
			tmp = num[i];
			ans[cnt] = num[i];
			check[i] = true;
			dfs(i, cnt + 1);
			check[i] = false;
		}
	}
}

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

	for (int i = 0; i < N; i++)
	{
		cin >> num[i];
	}
	sort(num, num + N); // 오름차순 정렬

	dfs(0, 0);
}
//https://cocoon1787.tistory.com/369

  내 생각과 다르게 n 크기의 배열만 가지고도 문제를 해결할 수 있었다. 위의 코드에서 변수 tmp가 중요한 역할을 한다.

우선 n만큼 숫자를 입력 받아 오름차순으로 정렬한다. 그 후 DFS함수 내의 반복문에서 DFS를 호출하며 수열들을 증가하는 순서로 출력한다. tmp ≠ num[i] 라는 조건은 한 노드를 방문하고 그 노드에서 DFS를 실행하는 반복문을 순회할 때 이전에 DFS를 실행했던 ‘num[i]’와(num[i-1]로 하면 방문했던 노드라서 건너뛰었을 경우 문제가 생긴다) 현재 num[i]가 같지 않도록 하는 것이다. 이는 오름차순으로 배열이 정렬되어있어서 가능한데, 예를 들어 9 7 1 9를 입력 받아 1 7 9 9로 정렬한 경우 1이 1→7을 방문하고 1→9를 두번 째로 방문한 다음 세 번째 1→9를 반복하는 것을 막아준다.