알고리즘(코딩테스트)

백트래킹

gbleem 2025. 3. 14. 12:05

1. 백트래킹

쉽게 말해서 가능한 모든 경우의 수를 다 해보는 알고리즘이다.

재귀 함수를 사용하여, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘!

 

문제를 보고, 주어진 전체 배열의 크기가 크지 않을 때 사용해 볼 법한 알고리즘이다.

(너무 큰 경우 시간 초과가 날 것이다)

 

가장 기본적인 형태로, N개 중 M개를 뽑는 문제가 존재한다.

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

 

코드 설명

  • 기본적으로 아래와 같은 형태로 재귀함수를 구성하게 된다.
  • isused 라는 이미 사용한 것인지를 체크하는 배열을 통해 중복을 제거하게 된다.
  • Choose라는 함수 안에서 경우의 수를 뽑는 과정이 이루어진다.
    • cur은 현재 뽑은 갯수가 되고, cur이 m이 되는 순간 특정 처리를 해주면 된다. (출력, 유효성 체크 등)
    • 아래 for문은 우리가 선택할 수의 범위가 되는데, 이 문제의 경우는 1부터 n까지의 숫자를 뽑을 수 있으므로 아래처럼 구성했다.
    • if문을 통해 중복체크를 해주고, answer라는 벡터에 값을 넣어주게 된다.
    • 또한 재귀함수가 종료되면서 isused를 false로 만들어주고, answer에서 pop_back 하는 과정을 통해 값을 리셋해주게 된다.
더보기 
#include <iostream>
#include <vector>
using namespace std;

int n, m;
int isused[10];
vector<int> answer;

void Choose(int cur)
{
	//길이가 m 이 되면 종료
	if (cur == m)
	{
		for (const auto& a : answer)
			cout << a << " ";
		cout << "\n";
		return;
	}
    
    //1 ~ n 의 숫자 중 하나를 선택
	for (int i = 1; i <= n; ++i)
	{
		if (!isused[i])
		{
			isused[i] = 1;
			answer.push_back(i);
			Choose(cur + 1);
			isused[i] = 0;
			answer.pop_back();
		}
	}
}

int main()
{
	cin >> n >> m;
	
	Choose(0);	
}

 

 

2. 예제 문제

문제 1) N-Queen

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

 

코드 설명

  • n이 주어졌을 때, 퀸이 서로를 공격하지 않도록 체크하려면
  • 먼저 같은 행에 존재하면 안된다. 그러나 행 체크는 단순히 행에는 하나만 둔다고 생각하면 된다.
    • 즉, Choose 함수의 cur값(매개변수) 을 x값(행)이라고 생각하면 된다.
    • 그렇게 되면 자동으로 N개의 행(행 값은 정해진 상태)에 y값을 어디에 둘 것인지만 체크하면 되기 때문이다.
    • 항상 이러한 좌표 문제에서 주의할 점은 행을 x라고 생각하고 열을 y라고 생각해야 한다는 점이다!!
  • 다음으로 같은 열에 존재하면 안된다. 열 체크는 isused1 이라는 배열을 통해 N개 만큼 체크해주면 된다.

  • 다음으로는 대각선에 대한 체크가 필요하다. 먼저 오른쪽 위로 올라가는 우대각 체크는 각 좌표의 x와 y값을 더한 값이 같은지 확인하면 된다.

  • 마지막으로 좌대각 체크가 필요하다. 이때는 x-y값이 같은지 체크하면된다. 단, 코드에 있어서 0보다 큰 값을 만들어주기 위해 n-1을 더해주었다.

더보기 
#include <iostream>
using namespace std;

int n;
int isused1[20];
int isused2[40];
int isused3[40];

int answer = 0;
void Choose(int cur) //cur : x값
{
	if (cur == n)
	{
		answer++;
		return;
	}

	//가로
	//우대각
	//좌대각
	for (int i = 0; i < n; ++i) //y값
	{
		if (isused1[i] || isused2[cur + i] || isused3[cur - i + n - 1])
			continue;
		isused1[i] = 1;
		isused2[cur + i] = 1;
		isused3[cur - i + n - 1] = 1;
		Choose(cur + 1);
		isused1[i] = 0;
		isused2[cur + i] = 0;
		isused3[cur - i + n - 1] = 0;
	}
}

int main()
{
	cin >> n;
	
	Choose(0);
	cout << answer;
}

 

문제2) 암호 만들기

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

 

코드 설명

  • 이 문제는 정석적인 백트래킹 방식에 추가적인 처리가 필요한 문제이다.
  • N개 중 M개를 뽑는 문제와 같은 틀로 시작을 하게 된다.
  • 추가 처리
    • 정답을 출력할 때 오름차순 정렬이 되야하기 때문에 char가 저장된 배열을 sort해서 시작한다.
    • 추가적으로 c개를 뽑는 도중에 오름 차순 정렬을 위해 answer.back() < board[i] 라는 조건을 추가해 주었다.
    • 마지막으로, 뽑은 char 배열에서 모음이 1개이상 자음이 2개 이상 들어가야 한다는 조건 때문에 Check() 라는 함수를 만들어서 조건을 만족시키게 하였다.
  • 주의점
    • c개를 뽑는 과정에서 오름차순 체크를 안하고, Check 함수에서 수행하니 시간 초과가 발생하였다.
더보기 
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int l, c;
char board[16];
unordered_map<char, int> isused;
vector<char> answer;

//오름차순이고, 최소 모음 한개 자음 두개
bool Check()
{
	int cnt1 = 0;
	int cnt2 = 0;

	for (const auto& a : answer)
	{
		if (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
			cnt1++;
		else
			cnt2++;		
	}

	if (cnt1 >= 1 && cnt2 >= 2)
		return true;

	return false;
}

void Choose(int cur)
{
	if (cur == l)
	{
		if (Check())
		{
			for (const auto& a : answer)
				cout << a;
			cout << "\n";
		}
		return;
	}

	for (int i = 0; i < c; ++i)
	{
		if (isused[board[i]] == 0)
		{
			if (answer.empty() || (!answer.empty() && (answer.back() < board[i])))
			{
				answer.push_back(board[i]);
				isused[board[i]] = 1;
				Choose(cur + 1);
				answer.pop_back();
				isused[board[i]] = 0;
			}
		}
	}

}


int main()
{
	cin >> l >> c;
	for (int i = 0; i < c; ++i)
	{
		cin >> board[i];
		isused[board[i]] = 0;
	}

	sort(board, board + c);
	//오름차순
	Choose(0);
}