[백준/C++] 15657 N과 M(8) (S3)

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

 

내 코드

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

using namespace std;

int arr[8];
int n, m;
int visited[8];

vector <int> box;

void DFS(int idx, int depth)
{
	
	if(depth == m)
	{
		for(int i=0;i<box.size();i++)
			cout<<box[i]<<" ";
		
		cout<<arr[idx];
		cout<<"\\n";
		return;
	}

	box.push_back(arr[idx]);
	
	for(int i= idx; i<n; i++)
	{
		if(visited[i])
			continue;
		else
		{
			DFS(i,depth+1);	
		}
	}
	
	box.pop_back();
}

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

  먼저 푼 “N과 M(5)” 문제에서 방문 했던 노드인지 체크하는 배열을 없애고 DFS를 호출하는 반복문이 현재 DFS의 파라미터 idx부터 시작하게 바꾸었다. 비오름차순은 n보다 n+1이 크거나 같아야 하므로 자기자신을 포함해서 증가하는 반복문으로 DFS를 호출하면 비오름차순의 조건을 만족할 수 있다.

다른 코드

#include <iostream>
#include <algorithm>

using namespace std;
#define MAX 9

int N,M;
int first[MAX];
int arr[MAX];

void dfs(int num, int k) { //현재 위치
    if(k==M) { //목표인 M까지 도달했다면
        for(auto i =0;i<M;i++)
            cout << arr[i] << " "; //arr에 저장한 값 M개 만큼 출력
        cout << "\\n";
    }else { //목표에 도달하지 않았다면
        for(auto i=num; i<N;i++) {
            arr[k]=first[i]; // 정렬한 N값을 arr에 저장
            dfs(i, k+1); //더 깊게 들어가자. (M까지)
        }
    }
}

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

    for(int i=0;i<N;i++)
        cin >> first[i];
    
    sort(first,first+N); //정렬

    dfs(0, 0);
}
//https://tooo1.tistory.com/323

  앞선 문제에서 봤던 다른 코드와 마찬가지로 내 코드랑 비슷한 차이점을 가진다. 차이를 이해했다고 생각했는데 막상 다시 짜려고 하니 잘 되지 않았다.

for문으로 DFS를 호출할때 호출하기에 앞서 for문의 반복자를 인덱스로 갖는 배열의 요소를 출력할 배열(혹은 벡터)에 넣어주는 것이 내 코드와의 중요한 차이다.

개선한 코드

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

using namespace std;

int arr[8];
int n, m;
int visited[8];

vector <int> box;

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

	//box.push_back(arr[idx]);
	
	for(int i= idx; i<n; i++)
	{
		box.push_back(arr[i]);
		
		DFS(i,depth+1);	
		
		box.pop_back();
	}
	
	
}

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

  DFS 한 번 호출로 모든 값이 출력되게 수정했다. DFS호출부에서 벡터 삽입/삭제가 일어나게 하고 depth > m일 때 vector에 저장된 수들을 출력하는 것으로 살짝 바꾸었다.