백트래킹

백트래킹이란?

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

• 재귀를 활용하기 때문에, 재귀의 특성상 틀리더라도 실수한 부분을 찾기가 정말 힘들다.
• 따라서 각자 문제를 많이 풀어봅시다.

오목를 두는 상황을 가정해보자! : 백트래킹의 적용된 예시

파랑돌이 빨강돌을 이길 수 있는 방법은 어떻게 생각해볼 수 있을까?
아래와 같은 상황에서 상대가 D5 좌표에다 빨강돌을 둔 경우, 우리는 어떻게 이길 수 있을지 생각해보자.

B5 (파랑) - F5 (빨강) - G5 (파랑) - F6 (빨강)
B5 (파랑) - F5 (빨강) - F6 (빨강) - G5 (파랑)

( 파랑돌이 F5 에 되는 경우는 각자 생각해봅시다. )

이번주 스터디 진행방식

1. N과 M 문제를 아무 힌트없이 풀어본다 ( 5분 )

2. 1차 힌트 및 접근법을 제공받고 다시 시도해본다 ( 10분 )

3. 2차 힌트 및 접근법을 제공받고 다시 시도해본다 ( 10분 )

4. 전체 코드를 제공받고 리뷰하는 방식으로 마무리 짓는다.

5. 마지막으로 재귀를 활용해 어떻게 백트래킹 유형을 어떻게 접근하는지 이해해본다.

문제

https://www.acmicpc.net/problem/15649

정답코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[10];
bool isused[10]; // 특정 수를 사용했는지 여부

// 현재 k개까지 수를 택한 상황에서 arr[k] 를 정하는 수
void func(int k) {
	if (k == m) {  // base condition : 만땅으로 m개를  택한 상황이 되었다면
		for (int i = 0; i < m; i++)   // 수열을 출력후 종료
			cout << arr[i] << ' ';
		cout << '\n';
	}

	// 1~n 까지의 수를 차례로 확인하며, 아직 쓰이지 않은 수를 찾아낸다.
	for (int i = 1; i <= n; i++) {
		if (!isused[i]) {
			arr[k] = i;  // k번째 수를 정함
			isused[i] = 1;  // 숫자 i를 (k번쨰 수)를 사용완료 상태로 체크
			func(k + 1);  // arr[k+1] 수, 즉 k+1번째 수를 정한다.
			isused[i] = 0; // 숫자 i의 상태를 다시 되돌린다. => 여기에 도달했다는것은 곧 arr[k] = i 로 둔 상태에서 
			// func(k+1) 에 들어갔다가 모든 과정을 끝냈다는 말이므로, isused[i] = false 로 되돌려서 숫자 i가 사용되지 않고 있음을 명시해준다.
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	func(0);
}