[백준/C++] 15654 N과 M(5) (S3)

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

 

 

내 코드

#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;
	}

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

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를 이용해야한다는 생각도 못했다. 전에 “N과M(1~4)”를 풀었어서 내가 제출했던 문제 소스를 보니 DFS를 사용했길래 그제서야 알았다. 경우의 수를 그래프로 표현해보면 DFS를 써야한다는 것을 금방 알 수 있다.

DFS로 방문한 적 없는 노드를 만날 때마다 vector에 넣어주고 depth가 m과 같아질 때의 함수가 vector에 있는 요소들 + 자신의 파라미터에 해당하는 요소를 출력한다. return 되어 낮은 depth에서 다시 탐색할 때를 위해 함수가 종료되기 전 visited = false로, vector에서 자신의 파라미터에 해당하는 요소를 빼준다. 간단한 DFS구현이지만 꽤 헤맸다.

다른 코드

//백준15654 N과 M (5)                                                        
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX = 8;
int N, M;
vector<int> list;
bool selected[MAX];
vector<int> ans;
 
void print() {
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << "\\n";
}
 
void DFS(int cnt) {
    if (cnt == M) {
        print();
        return;
    }
    for (int i = 0; i < N; i++) {
        if (selected[i]) continue;
        selected[i] = true;
        ans.push_back(list[i]);
        DFS(cnt + 1);
        ans.pop_back();
        selected[i] = false;
    }
}
 
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        list.push_back(n);
    }
 
    sort(list.begin(), list.end());
 
    DFS(0);
 
    return 0;
}
//https://scarlettb.tistory.com/131

나는 DFS의 시작 노드를 for문으로 하나씩 직접 지정해 DFS를 N번 실행하는 방법을 썼다.

코드를 짜면서도 이럴 필요 없는 방법이 있을거라는 생각이 들었다.

위의 코드의 DFS함수가 호출되는 부분을 보면 main 함수에서는 DFS(0)으로 시작하고 DFS(0)의 반복문에서는 모든 노드들이 미방문(selected = false)상태이므로 DFS(1, 2 , 3, …)을 실행하게 된다.

즉 나는 DFS(0), depth가 0인 상태를 생략하고 직접 depth가 1인 모든 상태를 실행해준 것, 위의 코드는 depth=0부터 알아서 depth=1을 찾아가게 한 것이다.