Backtracking : N과 M 시리즈

게시 2023/11/01 업데이트 2024/06/17

By Dukgukim

백트래킹이란?

완전탐색 방법 중 하나

백트래킹 : 완전탐색의 아이디어에서 불필요한 분기를 가지치기 하는 것

정답을 도출하기 전 탐색과정 주에 정답이 될 수 없는 조건에 해당하면 가지치기를 하여 효율을 높힘

재귀함수, 백트래킹을 연습하기에 가장 좋은 문제 모음

N과 M 시리즈 문제집

간단 설명

1번부터 시작해서 12번까지 존재

난이도를 점점 높혀가면서 백트래킹을 연습하는 문제

문제가 미세하게 다르므로 그 차이점을 잘 살펴볼 것

알고리즘 문제들이 조합인지, 순열인지를 구분하는 문제를 제출하므로 차이를 잘 알아야한다

주의점

가지치기 조건에 꼭 return을 써줄 것
언제 return을 쓸지 말지 고민할 것

문제

0. 백트래킹의 기본 뼈대 구조

N개의 원소중 중복을 허용하여 하나를 선택. 출력시 중복되는 순열도 상관없이 출력한다
이 기본 구조에서 하나씩 덧붙여가며 난이도가 높아짐

  
int path[MAX]; // 지금까지 온 경로를 적어두는 배열. 원소를 쭉 출력해야 하는 경우 필요함

void DFS(int level){
    // 종료 조건 <- 탈출 조건, 기저조건이라고도 부름. 없으면 무한루프에 빠지므로 주의
    if(level == M){
        // 종료 조건에서 보통 결과를 출력한다. path의 내용을 쭉 출력하면됨        
        return;
    }

    // 여기서부터 DFS 가지로 나뉘어진다
    for(int i=0; i<N; i++){ // N개의 원소중 하나를 선택한다
        path[level] = arr[i]; // 현재 레벨에 선택한 원소를 넣고
        DFS(level+1); // DFS를 재귀적으로 호출해준다
        path[level]= 0; // 원상복구 해준다
    }
}

/*
1 1, 1 2, 1 3, 1 4,
2 1, 2 2, 2 3, 2 4,
...
4 1, 4 2, 4 3, 4 4
가 출력됨
*/

1. N과 M (1)

N과 M(1)

순열 (nPm)을 구하는 문제
서로 다른 n개 중에 m개를 선택하는 경우의 수. (순서 상관 있음)
- 즉, {1,1,2}와 {1,2,1}은 다른 수열임
원소의 중복을 허용하지 않음 -> 방문을 체크하는 used 배열을 별도로 관리

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
int used[10]; // 해당 숫자의 사용 여부를 기록하는 배열 used[1] == 1인 경우, 1은 이미 사용된 것
int path[10]; // 정답을 기록하는 배열

void run(int level) {
	if (level > M) {
		for (int i = 1; i <= M; i++) {
			cout << path[i] << ' ';
		}
		cout << '\n'; // endl을 쓰면 시간 초과 발생
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (used[i] == 1) continue; // 이미 사용한 수인지 중복을 체크

		// 사용하지 않은 수라면 
		used[i] = 1; // 사용 표시 후
		path[level] = i; // path에 기록해둔다

		// 다음 넣을 숫자를 확인
		run(level + 1);
		
		// 나왔다면 다시 원상복구
		used[i] = 0;
	}
}

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

	run(1);

	return 0;
}

endl과 \n의 차이는 해당 글을 참조

2. N과 M (2)

N과 M(2)

1에서 오름차순으로 출력해야하는 조건이 추가됨
중복 없이(used 이용)
2가지 방법이 있음
1. 조합(combination)으로 처리하는 방법. (nCm)
2. 가지치기 조건을 추가해서 처리하는 방법

조합은 나중에 한번 더 다룰 예정이므로, 2번으로 처리함

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
int used[10];
int path[10];

void run(int level) {
	// 가지치기 조건 1. 방금 추가한 숫자가, 이전 숫자보다 작은 경우 오름차순이 아니므로 돌아감
	if (level == 2 && path[level - 2] > path[level - 1]) return; 
	if (level == M) {
		for (int i = 0; i < M; i++) {
			cout << path[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (used[i] == 1) continue;
				used[i] = 1;
		path[level] = i;

		run(level + 1);
		// 원상복구
		used[i] = 0;
	}
}

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

	run(0);

	return 0;
}

3. N과 M (3)

N과 M (3)

가장 기본 뼈대와 구조가 같은 기초 문제
같은 수를 여러번 골라도 되는 순열
중복 조합 nHm
cin, cout 사용시 속도에 주의할 것

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
int path[10];
// 별도로 중복 체크할 필요 없으므로 used를 사용하지 않음

void run(int level) {
	if (level == M) {
		for (int i = 0; i < M; i++) {
			cout << path[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= N; i++) {
		path[level] = i;
		run(level + 1);
	}
}

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

	run(0);

	return 0;
}

4. N과 M (4)

N과 M(4)

1~N까지의 자연수 중, M개 고르기
중복을 허용하고
비내림차순이여야한다. 오름차순과는 다름
- 오름차순은 1,2,3,4고, 비내림차순은 1,1,1,1도 허용함
- 자세한 내용은 링크 참조
3번 문제와 4번 문제의 퓨전버전

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
int path[10];

void run(int level) {
	if (level >= 2 && path[level - 2] > path[level - 1]) return;
	if (level == M) {
		for (int i = 0; i < M; i++) {
			cout << path[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= N; i++) {
		path[level] = i;
		run(level + 1);
	}
}

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

	run(0);

	return 0;
}

5. N과 M (5)

N과 M(5)

원소가 들어있는 집합을 이용해 순열 생성하기
중복을 허용하지 않음. 순서 상관있음!

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;
int used[9];
vector<int> path;

void run(int level) {
	if (level == M) {
		for (int e : path) {
			cout << e << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < N; i++) {
		if (used[i] == 1) continue;
		// 들어가기 전 세팅
		used[i] = 1;
		path.push_back(v[i]);
		// 레벨 1 증가
		run(level + 1);
		// 원상복구
		used[i] = 0;
		path.pop_back();
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;

	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	
	run(0);

	return 0;
}

  
// 벡터를 사용하지 않는 버전
int arr[10];  
int path[10];
int used[10];

void permutation(int level) {
	if (level == M) {
		for (int i = 0; i < M; i++) {
			cout << path[i] << " ";
		}
		cout << '\n';
		return;
	}

	// arr 배열의 원소 N개 중 하나 선택
	for (int x = 0; x < N; x++) {
		if (used[x] == 1) continue;

		path[level] = arr[x]; // arr원소의 값을 넣는다
		used[x] = 1;

		permutation(level + 1);

		path[level] = 0;
		used[x] = 0;

	}
}

algorithm 헤더의 next_permutation를 이용해 해결할수도 있음

  
int main() {

  int n, m;
  cin >> n >> m;

  vector<int> pArr(n, 0);

  for (int i = 0; i < n; i++)
      cin >> pArr[i];
	
  sort(pArr.begin(), pArr.end()); // !!필수!! : next_permutation 사용을 위해선 오름차순으로 정렬을 해줘야함.

      do
      {
          for (int i = 0; i < m; i++) // m개만큼 선택 후 출력
              cout << pArr[i] << " ";
          cout << '\n';

          reverse(pArr.begin() + m, pArr.end()); 
          // reverse를 사용하는 이유는 나중에 따로 포스팅함
          // 일단은 m만큼 이동후 reverse해준다는걸 알아두기

      } while (next_permutation(pArr.begin(), pArr.end()));
}

6. N과 M (6)

N과 M(6)

제공된 배열에서 원소를 골라 조합 만들기
N개의 자연수 중에서 M개를 고르는 수열
원소의 중복을 허용하지 않고, 중복되는 수열을 여러번 출력하면 안되며, 오름차순이여야 한다
N과 M (2)에서는 가지치기를 이용했지만 여기서는 조합을 이용해 봄

  
#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int arr[9];
int path[9];
// 별도의 중복 체크 배열 불필요. 원소를 체크할 때, 자기 다음번호부터 확인함

void combination(int level, int start) {
	if (level == M) {
		for (int i = 0; i < level; i++) {
			cout << path[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = start; i < N; i++) {
		path[level] = arr[i];

		combination(level + 1, i+1); // i+1로, 자기 자신은 건너 뛰고 다음 원소부터 접근 가능함

		path[level] = 0;
	}s

}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N);

	combination(0, 0);

	return 0;
}

오름차순으로 정렬해두어야 비내림차순으로 출력이 가능함

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;
int used[10];
vector<int> path;

void run(int level) {
	if (level >= 2 && path[level - 2] > path[level - 1]) return;
	if (level == M) {
		for (int e : path) {
			cout << e << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < N; i++) {
		if (used[i] == 1) continue;
		used[i] = 1;
		path.push_back(v[i]);

		run(level + 1);

		used[i] = 0;
		path.pop_back();
	}
}

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

	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	
	run(0);

	return 0;
}

가지치기 버전

7. N과 M (7)

N과 M(7)

중복 허용. N개의 원소중 M개 선택.
대신 원소 집합 제공됨

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;
vector<int> path;

void run(int level) {
	if (level == M) {
		for (int e : path) {
			cout << e << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < N; i++) {
		path.push_back(v[i]);

		run(level + 1);

		path.pop_back();
	}
}

int main() {
	cin >> N >> M;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	run(0);

	return 0;
}

  
int N, M;
int arr[8];
int path[8];

void permutation(int level) {
	if (level == M) {
		for (int i = 0; i < level; i++) {
			printf("%d ", path[i]);
		}
		printf("\n");
		return;
	}

	for (int x = 0; x < N; x++) {

		path[level] = arr[x];
		permutation(level + 1);
		path[level] = 0;

	}
}

8. N과 M (8)

N과 M(8)

N개의 자연수 중에서 M개를 고르는 수열
중복 허용
고른 수열은 비내림차순 <- 조합 이용

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;
vector<int> path;

void combination(int level, int start) {
	if (level == M) {
		for (int e : path) {
			cout << e << ' ';
		} cout << '\n';
		return;
	}
	for (int i = start; i < N; i++) {
		path.push_back(v[i]);

		combination(level + 1, i); // 오름차순이 아닌, 비내림차순이므로 i와 같은수도 포함한다

		path.pop_back();
	}
}

int main() {
	cin >> N >> M;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	
	combination(0, 0);

	return 0;
}

9. N과 M (9)

N과 M(9)

N개의 자연수 중에서 M개를 고르는 수열
N과 M중에서 가장 낮은 정답률을 기록하는 어려운 문제다
중복되는 수열을 여러번 출력하면 안된다
- {1, 7, 9, 9}에서 2개를 뽑는 경우,
첫번재 9를 뽑는 {1, 9}와 두번째 9를 뽑는 {1, 9}는 같은 수열로 취급함.
- 이를 어떻게 구분할 것인가?
  - 마지막에 경로에 넣은 원소를 저장해두고, 이와 같은 원소를 넣으려하면 가지치기한다.
  아래 블로그에 자세한 설명을 해주신분이 있으므로 링크

  
void DFS(int level) {
	if (level == M) {
		for (int i = 0; i < level; i++) {
			cout << path[i] << " ";
		}
		cout << endl;
		return;
	}
	int last_num = 0; // 마지막으로 경로에 넣은 원소를 기록해둔다. 

	for (int x = 0; x < N; x++) {
		if (used[x] == 1) continue; 
		if (last_num == arr[x]) continue; // 마지막에 넣었던 숫자랑, 현재 넣을 숫자랑 같으면 패스
		path[level] = arr[x];
		used[x] = 1;
		last_num = arr[x]; // 마지막으로 넣은 숫자 기록

		DFS(level + 1);
		path[level] = 0;
		used[x] = 0;
	}

}

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;
int used[10];
vector<int> path;


void run(int level) {
	if (level == M) {
		for (int e : path) {
			cout << e << ' ';
		} cout << '\n';
		return;
	}
	int last_num = 0;
	for (int i = 0; i < N; i++) {
		if (used[i] == 1) continue;
		if (last_num == v[i]) continue;

		used[i] = 1;
		path.push_back(v[i]);
		last_num = v[i];

		run(level + 1);

		used[i] = 0;
		path.pop_back();

	}
}

int main() {
	cin >> N >> M;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	run(0);

	return 0;
}

10. N과 M (10)

N과 M(10)

N개의 자연수 중에서 M개를 고른 수열
고른 수열은 비내림차순이어야 한다 => 조합
9번과 마찬가지로 중복되는 수열을 여러번 출력하면 안된다

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;
int used[10];
vector<int> path;

void run(int level, int start) {
	if (level == M) {
		for (int e : path) {
			cout << e << ' ';
		} cout << '\n';
		return;
	}
	int last_num = 0;
	for (int i = start; i < N; i++) {
		if (used[i] == 1) continue;
		if (last_num == v[i]) continue;

		used[i] = 1;
		path.push_back(v[i]);
		last_num = v[i];
		
		run(level + 1, i);

		used[i] = 0;
		path.pop_back();
	}
}

int main() {
	cin >> N >> M;
	v.resize(N);
	for (int i = 0; i < N; i++)
		cin >> v[i];

	sort(v.begin(), v.end());

	run(0, 0);

	return 0;
}

11. N과 M (11)

N과 M(11)

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다
중복되는 수열을 여러번 출력하면 안된다.

10번과 다른점은, 중복을 허용하고, 오름차순이 아니라는 것

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;
vector<int> path;

void run(int level) {
	if (level == M) {
		for (int e : path) {
			cout << e << ' ';
		} cout << '\n';
		return;
	}
	int last_num = 0;
	for (int i = 0; i < N; i++) {
		if (last_num == v[i]) continue;

		
		path.push_back(v[i]);
		last_num = v[i];
		
		run(level + 1);

		path.pop_back();
	}
}

int main() {
	cin >> N >> M;
	v.resize(N);
	for (int i = 0; i < N; i++)
		cin >> v[i];

	sort(v.begin(), v.end());

	run(0);

	return 0;
}

12. N과 M (12)

N과 M(12)

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다

  
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;
vector<int> path;

void run(int level, int start) {
	if (level == M) {
		for (int e : path) {
			cout << e << ' ';
		} cout << '\n';
		return;
	}
	int last_num = 0;
	for (int i = start; i < N; i++) {
		if (last_num == v[i]) continue;
		path.push_back(v[i]);
		last_num = v[i];

		run(level + 1, i);

		path.pop_back();
	}
}

int main() {
	cin >> N >> M;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	run(0, 0);

	return 0;
}

  
#include <iostream>
#include <algorithm>

#define MAX 9

using namespace std;

int N, M;
int path[MAX];
int tmp[MAX], arr[MAX], idx = 0;

void combination(int level, int start) {
	if (level >= M) {
		for (int i = 0; i < level; i++) {
			printf("%d ", path[i]);
		}
		printf("\n");
		return;
	}
	for (int t = start; t <= idx; t++) {
		path[level] = arr[t];
		combination(level + 1, t); // 중복을 허용하므로, 다음 DFS의 start는 t도 허용한다 
		path[level] = 0;
	}
}

int main() {
	// freopen_s(new FILE*, "sample_input.txt", "r", stdin);
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%d", &tmp[i]);
	}
	sort(tmp, tmp+ N);
	arr[0] = tmp[0];
	// 원소의 중복을 제거
	for (int i = 1; i < N; i++) {
		if (tmp[i - 1] == tmp[i]) continue;
		arr[++idx] = tmp[i];
	}

	combination(0, 0);

	return 0;
}

/*
입력 > 
4 2
9 7 9 1
출력 > 
1 1
1 7
1 9
7 7
7 9
9 9
*/

아예 중복 원소를 넣지 않는 방법

굉장히 많은 경우의 수가 있으므로 꼭 다시 정리해볼 것

참고 : https://covenant.tistory.com/123

https://velog.io/@yongin01/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EB%B0%B1%EC%A4%80-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-%EB%AC%B8%EC%A0%9C%EC%B6%94%EC%B2%9C

https://flowersayo.tistory.com/84

2024.06.17 수정

Algorithm, Problem Solving

backtracking bruteforce