[코딩 테스트 준비 - 기초] 4. 브루트 포스 - N과 M & NM과 K

1. 재귀함수 작성 방법

• 재귀함수는 i 번째 방법과 i+1 번째 방법의 패턴이 동일한 경우 사용한다.
• 다음으로 넘어갈 때 변화하는 것에 집중해 이를 함수의 인자로 만들거나 따로 관리해야 한다.

구현 Point

1. 재귀함수 호출 전, 그 함수를 호출하기 위한 상태를 미리 준비해둬야 한다.
2. 재귀함수 호출이 끝난 것은 해당 경우가 끝난 것으로, 원 상태로 돌려줄 필요가 있다.
3. 재귀의 종료 조건을 설정하는 것이 중요하다.

 

2. N과 M

[백준 15649 N과 M(1)]

• index번 위치에 올 수 있는 수를 결정하는 함수를 재귀함수로 작성한다.
• 1번 위치에서 2번 위치로 넘어갈 때 변화하는 것은 위치와 앞에서 1번 위치에서 사용한 숫자 i의 사용 여부이다.
• 벡터를 사용하기 때문에 배열의 현재 위치를 따로 관리하지 않아도 되며, i의 사용 여부는 전역으로 관리한다.

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

vector<int> v;
bool visited[10];

void backtrack(int cur, int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=1; i<=n; i++){ //1부터 n까지 수 중 선택
		if(!visited[i]){ //i가 앞에서 사용되지 않았다면
			//재귀 호출 전 상태 준비
			visited[i] = true;
			v.push_back(i);

			backtrack(cur + 1, n, m);

			//재귀 호출 후 원 상태로 돌리기
			visited[i] = false;
			v.pop_back();
		}
	}
}

int main(){
	int n, m;
	cin>>n>>m;
	backtrack(0, n, m);
	return 0;
}

 

[백준 15650 N과 M(2)]

• 위 소스코드와 매우 유사하다. 1번 위치에서 2번 위치로 넘어갈 때 변화하는 것에 범위의 시작 값을 추가하면 된다.
• 범위의 시작을 관리하기 위해 cur을 사용했고 이는 현재 선택한 숫자를 의미한다. (사실 위 코드에서 cur인자는 필요하지 않다. 지금 코드와 비교하기 위해 넣어두었다.)
• 참고) 선택의 문제로도 풀 수 있다. -> O(2^n)

void backtrack(int cur, int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=cur; i<=n; i++){ //cur부터 n까지 수 중 선택
		if(!visited[i]){
			//재귀 호출 전 상태 준비
			visited[i] = true;
			v.push_back(i);

			backtrack(i + 1, n, m); //다음 위치에서는 방금 선택한 i보다 큰 수 중에 선택 가능

			//재귀 호출 후 원 상태로 돌리기
			visited[i] = false;
			v.pop_back();
		}
	}
}

//backtrack(1, n, m)

 

• 오름차순 출력의 특성 상 배열 visited없이 작성할 수도 있다. 앞에서 결정된 숫자보다 큰 범위에서 다음 숫자를 결정해야 하기 때문이다. 따라서 아래처럼 써도 된다.

void backtrack(int cur, int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=cur; i<=n; i++){ //cur부터 n까지 수 중 선택 가능
          v.push_back(i);
          backtrack(i + 1, n, m);
          v.pop_back();
	}
}

// backtrack(1, n, m);

 

[백준 15651 N과 M(3)]

• 각 자리수가 가질 수 있는 숫자는 모두 1~N의 값이다.
• 앞에서 선택한 수는 다음 위치에서 선택할 값에 영향을 미치지 않기 때문에 visited가 필요없다.

void backtrack(int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=1; i<=n; i++){ //1부터 n까지 수 중 선택 가능
		v.push_back(i);
		backtrack(n, m);
		v.pop_back();
	}
}

 

[백준 15652 N과 M(4)]

• 2번과 유사하다. 앞서 선택한 값이 다음 선택에 영향을 미치므로 visited는 필요없다.
• 재귀함수를 호출할 때 현재 선택한 값보다 크거나 같은 수의 범위에서 선택하도록 i를 넘긴다.

void backtrack(int cur, int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=cur; i<=n; i++){ //cur부터 n까지 수 중 선택 가능
		v.push_back(i);
		backtrack(i, n, m); //다음 위치에서는 방금 선택한 i보다 크거나 같은 수 중에 선택 가능
		v.pop_back();
	}
}

 

[백준 15652 N과 M(5)]

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

vector<int> v;
vector<int> arr;
bool visited[10]; //arr의 idx를 기준으로 방문여부 판단

void backtrack(int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=0; i<n; i++){
		if(!visited[i]){
			visited[i] = true;
			v.push_back(arr[i]);
			backtrack(n, m);
			visited[i] = false;
			v.pop_back();
		}
	}
}

int main(){
	int n, m;
	cin>>n>>m;

	int x;
	for(int i=0; i<n; i++){
		cin>>x;
		arr.push_back(x);
	}

	sort(arr.begin(), arr.end());
	backtrack(n, m);

	return 0;
}

 

[백준 15652 N과 M(6)]

void backtrack(int idx, int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=idx; i<n; i++){
		v.push_back(arr[i]);
		backtrack(i+1, n, m);
		v.pop_back();
	}
}


//sort(arr.begin(), arr.end());
//backtrack(0, n, m);

 

[백준 15652 N과 M(7)]

void backtrack(int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=0; i<n; i++){
		v.push_back(arr[i]);
		backtrack(n, m);
		v.pop_back();
	}
}

//sort(arr.begin(), arr.end());
//backtrack(n, m);

 

[백준 15652 N과 M(8)]

void backtrack(int idx, int n, int m){
	if((int)v.size() == m){ //재귀 종료 조건
		for(int i=0; i<m; i++)
			cout<<v[i]<<" ";
		cout<<'\n';
		return;
	}
	for(int i=idx; i<n; i++){
		v.push_back(arr[i]);
		backtrack(i, n, m);
		v.pop_back();
	}
}

//sort(arr.begin(), arr.end());
//backtrack(0, n, m);

 

 

3. NM과 K

[백준 18290 NM과 K(1)]

• cnt는 선택한 칸의 수, sum 선택한 값의 총합이다. 이를 재귀 함수의 인자로 사용한다.
• px와 py는 중복을 피하기 위한 추가적인 인자이다. 이전에 확인한 칸을 다음 재귀에서 선택하지 않도록 한다.

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

bool visited[11][11];
int arr[11][11];
int n, m, k;
int ans =  -40000;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void backtrack(int px, int py, int cnt, int sum){
	if(cnt == k){ //재귀 종료 조건
		ans = max(ans, sum);
		return;
	}
	for(int x=px; x<n; x++){
		for(int y=(x == px ? py : 0); y<m; y++){
			if(!visited[x][y]){
				bool flag = true;
				for(int i=0; i<4; i++){ //인접 여부 판단
					int nx = x + dx[i];
					int ny = y + dy[i];
					if(0 <= nx && nx < n && 0 <= ny && ny < m){ //범위 내에 존재 -> 선택 가능한 경우
						if(visited[nx][ny])	flag = false; //이미 방문한 칸이면 선택 불가
					}
				}
				if(flag){
					visited[x][y] = true;
					backtrack(x, y, cnt + 1, sum + arr[x][y]);
					visited[x][y] = false;
				}
			}
		}
	}

}

int main(){
	cin>>n>>m>>k;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++)
			cin>>arr[i][j];
	}
	backtrack(0, 0, 0, 0);
	cout<<ans<<'\n';
	return 0;
}

 

재귀 함수의 이중 for문에서 x=0, y=0으로 시작해도 되지만, 이 경우 재귀함수가 호출될 때마다 중복된 값을 검사하기 때문에 시간복잡도가 매우 커진다. 아래 그림은 x=0, y=0으로 했을 때의 시간과 위 코드의 시간 차이로 윗 부분이 위 코드의 결과이다.