백트래킹 문제들

#15649

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

bool visited[9] = { 0 };
int arr[9] = { 0 };
vector<int> print;

void dfs(int start, int n, int m)
{
	//끝까지 왔다면
	if (start == m)
	{
		for (int i = 0; i < print.size(); i++)
		{
			cout << print[i] << " ";
		}
		cout << "\n";
	}

	for (int i = 1; i<=n; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			print.push_back(i);
			dfs(start + 1, n, m);
			print.pop_back();
			visited[i] = false; //해제해주기
		}
	}
}

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

	dfs(0, N, M);	
}

#15650

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

bool visited[9] = { 0 };
int arr[9] = { 0 };
vector<int> print;

void dfs(int start, int num, int n, int m)
{
	//끝까지 왔다면
	if (start == m)
	{
		for (int i = 0; i < print.size(); i++)
		{
			cout << print[i] << " ";
		}
		cout << "\n";
	}

	for (int i = num; i <= n; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			print.push_back(i);
			dfs(start + 1, i+1, n, m);
			print.pop_back();
			visited[i] = false; //해제해주기
		}
	}
}


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

	dfs(0, 1, N, M);
}

#15651

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

bool visited[9] = { 0 };
int arr[9] = { 0 };
vector<int> print;

void dfs(int start, int n, int m)
{
	//끝까지 왔다면
	if (start == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << print[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		visited[i] = true;
		print.push_back(i);
		dfs(start + 1, n, m);
		print.pop_back();
		visited[i] = false; //해제해주기
	}
}

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

	dfs(0, N, M);
}

#15652

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

bool visited[9] = { 0 };
int arr[9] = { 0 };
vector<int> print;

void dfs(int start, int num, int n, int m)
{
	//끝까지 왔다면
	if (start == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << print[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = num; i <= n; i++)
	{
		visited[i] = true;
		print.push_back(i);
		dfs(start + 1, i, n, m);
		print.pop_back();
		visited[i] = false; //해제해주기
	}
}

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

	dfs(0, 1, N, M);
}

#9663

#include <iostream>
#include <cmath>

using namespace std;

int col[15] = { 0 };
int N, cnt = 0;

bool check(int level)
{
	for (int i = 0; i < level; i++)
	{
		//만약 퀸이 같은 level에 있거나 대각선에 있다면
		if (col[i] == col[level] || abs(col[i] - col[level]) == abs(i - level))
		{
			return false;
		}
	}
	return true;
}

void nqueen(int num)
{
	//총 배치 수가 N이 되면 cnt+1
	if (num == N)
		cnt++;
	else
	{
		for (int i = 0; i < N; i++)
		{
			col[num] = i;
			if (check(num))
				nqueen(num + 1);
		}
	}
}

int main()
{
	//todo
	//1. array에 퀸들이 있는 위치 저장 -> 1차배열사용
	//2. 대각선 또는 같은 줄에 있는지 체크
	//대각선에 있다는 것은 좌표의 x값의 변화량과 y값의 변화량이 같다는 뜻

	cin >> N;

	nqueen(0);

	cout << cnt;

}

#14888

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

int N;
int num[11] = { 0 }; // 수열 
int operators[4]; // 연산자의 개수
int min_ = 1000000001;
int max_ = -1000000001;

void calculate(int index, int result)
{
	if (index == N) 
	{
		if (result > max_)
			max_ = result;
		if (result < min_)
			min_ = result;
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		if (operators[i] > 0)
		{
			operators[i]--;

			if (i == 0) // 덧셈
			{
				calculate(index + 1, result + num[index]);
			}
			else if (i == 1) // 뺄셈
			{
				calculate(index + 1, result - num[index]);
			}
			else if (i == 2) // 곱셈
			{
				calculate(index + 1, result * num[index]);
			}
			else // 나눗셈 
			{
				calculate(index + 1, result / num[index]);
			}

			operators[i]++; //다음에도 써줘야 하므로
		}
	}
	return;
}

int main()
{
	cin >> N;
	
	for (int i = 0; i < N; i++)
		cin >> num[i];
	
	for (int i = 0; i < 4; i++)
		cin >> operators[i];

	calculate(1, num[0]);

	cout << max_ << "\n";
	cout << min_;
	return 0;
}

#14889

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

int N;
int min_ = 999999;
int arr[20][20] = { 0 };
bool visited[20];

void dfs(int cnt, int index)
{
	vector<int> start;
	vector<int> link;
	int start_score = 0;
	int link_score = 0;

	if (cnt == N / 2)
	{
		//depth가 N/2가 되면 멈추기
		//팀 나누기 -> 방문 했었다면 start팀으로, 방문 안했다면 link 팀으로
		//팀끼리 합 구해서 최저값 구하기

		for (int i = 0; i < N; i++)
		{
			if (visited[i])
			{
				start.push_back(i);
			}
			else
				link.push_back(i);
		}

		//각 팀의 총합 구하기
		for (int i = 0; i < N / 2; i++)
		{
			for (int j = 0; j < N / 2; j++)
			{
				start_score += arr[start[i]][start[j]];
				link_score += arr[link[i]][link[j]];
			}
		}

		if (abs(start_score - link_score) < min_)
		{
			min_ = abs(start_score - link_score);
		}
		return;
	}

	for (int i = index; i < N; i++)
	{
		if (visited[i])
			continue;
		else
		{
			visited[i] = true;
			dfs(cnt + 1, i);
			visited[i] = false;
		}
	}
}


int main()
{
	//todo
	//1. 이차원 array 만들어서 입력받기
	//2. Sij + Sji과 S(N-i)(N-j) + S(N-j)(N-i) 차이의 최솟값 구하기 
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
		}
	}

	dfs(0, 0);
	cout << min_;
	return 0;
}