이것 저것 &

문제링크:www.acmicpc.net/problem/2239

일반적인 스도쿠문제와 동일합니다.

 다만,  "제일 작은 경우를 출력한다." 라는 조건이 추가됐습니다.

아래 링크와 같은 방법으로 해결해도 됩니다. 

gusdnr69.tistory.com/142

저는 직관적인 방법으로 결과를 도출했습니다.

아래는 정답 코드 입니다.

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

int arr[9][9] = { 0, };
bool fin = false;
vector <pair <int, int>> zero_vec;

void dfs(int cnt) {
	if (cnt == zero_vec.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << arr[i][j];
			cout << endl;
		}
		fin = true;
		return;
	}
	if (fin == true)
		return;

	for(int i=cnt;i<zero_vec.size();i++){}
	int y = zero_vec[cnt].first;
	int x = zero_vec[cnt].second;

	bool temp[10] = { 0, };
	for (int i = 0; i < 9; i++) {
		temp[arr[y][i]] = 1;
		temp[arr[i][x]] = 1;
	}
	for (int i = y / 3 * 3; i < y / 3 * 3 + 3; i++)
		for (int j = x / 3 * 3; j < x / 3 * 3 + 3; j++)
			temp[arr[i][j]] = 1;

	for (int i = 1; i <= 9; i++)
		if (temp[i] == 0) {
			arr[y][x] = i;
			dfs(cnt + 1);
			arr[y][x] = 0;
		}


}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	for (int i = 0; i < 9; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < 9; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 0)
				zero_vec.push_back(make_pair(i, j));
		}
	}
	dfs(0);

	return 0;
}

문제링크:www.acmicpc.net/problem/2529

algorithm 라이브러리에서 제공하는 순열 함수를 사용하여 해결했습니다.

k+1개의 수를 만든 다음 큰 수부터 작은 수순으로, 그리고 작은 수부터 큰 수순으로 차례대로 결과값이 될 수 있는지 확인해주면 결과를 도출했습니다.

처음에 재귀함수로 접근하려고 했는데 생각해보니 굳이 필요없을 것 같습니다. 

아래는 정답코드입니다.

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

int k;
vector <char> arr;
vector <int> val;
bool chk() {

	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] == '<') {
			if (val[i] > val[i + 1])
				return false;
		}
		else {
			if (val[i] < val[i + 1])
				return false;
		}
	}
	return true;
}


int main() {

	cin >> k;
	for (int i = 0; i < k; i++) {
		char temp;
		cin >> temp;
		arr.push_back(temp);
	}
	for (int j = 0, i = 9; j < k + 1; j++,i--) 
		val.push_back(i);
	while (1) {
		if (chk() == true)
			break;
		prev_permutation(val.begin(), val.end());
	}
	for (int i = 0; i < val.size(); i++)
		cout << val[i];
	cout << endl;

	val.clear();
	for (int i = 0; i < k + 1; i++)
		val.push_back(i);

	while (1) {
		if (chk() == true)
			break;

		next_permutation(val.begin(), val.end());
		
	}
	for (int i = 0; i < val.size(); i++)
		cout << val[i];
	cout << endl;
	return 0;

}

문제링크: www.acmicpc.net/problem/1799

백트래킹문제입니다. 체스판 크기가 최대 10x10입니다. 그렇기 때문에 가지치기를 통해서 반복 횟수를 줄여주어야 합니다.

• 1. 비숍특성상 검은칸에서 시작하면 검은칸으로만 흰칸에서 시작하면 흰칸으로만 이동가능합니다.
• 2. 그렇기 때문에 흰색과 검은색을 각각 구분합니다. (행 +열이 짝수면 흰색 아니면 홀수면 검은색)
• 2. 각각 비숍을 둘 수 있는지 확인합니다. (abs(arr[cur].y - bitshop[j].y) = abs(arr[cur].x - bitshop[j].x) 면 대각선에 비숍이 있는 것)

아래는 정답코드입니다. 천천히 확인해보세요.

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

typedef struct MyStruct
{
	int y;
	int x;
}chess;
int n = 0, result = 0;
int temp[11][11];
vector <chess> arr; //1인 곳
vector <chess> bitshop; // 비숍저장

void dfs(int cnt, int cur) {// 비숍개수, 현재 탐색 위치 순

	if (cnt > result) {
		result = cnt;
	}
	if (cur == arr.size())
		return;

	//1. 비숍가능한지 검사
	bool jud = true;
	for (int j = 0; j < bitshop.size(); j++) {
		if (abs(arr[cur].y - bitshop[j].y) == abs(arr[cur].x - bitshop[j].x)) {
			jud = false;
			break;
		}
	}
	if (jud == true) { //비숍이 가능하다면 
		bitshop.push_back({ arr[cur].y,arr[cur].x });
		dfs(cnt + 1, cur + 1);
		bitshop.pop_back();
	}
	dfs(cnt, cur + 1);

	return;

}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	int answer = 0;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			cin >> temp[i][j];
			if (temp[i][j] == 1 && (i+j)%2 == 0)
				arr.push_back({ i,j });
		}

	dfs(0, 0);
	answer += result;
	result = 0;
	arr.clear();


	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (temp[i][j] == 1 && (i + j) % 2 == 1)
				arr.push_back({ i,j });
		}
	dfs(0, 0);
	answer += result;
	cout << answer << endl;

	
	return 0;
}

문제링크:www.acmicpc.net/status?user_id=gusdnr9875&problem_id=15918&from_mine=1

백트래킹 문제입니다. dfs를 통해 구현하는데 이때 문제 조건에 맞게 가지치기를 해주어야 합니다.

가지치기 

• 1. x,y가 주어지기 때문에 위치를 정할 수 있습니다. ex) x,y가 1,5라면 5 - 1 - 1 = 3. 즉 3이 x, y 위치에 고정됩니다.
• 2. 2*n개인 위치를 반복할때, arr[현재] 가 1이거나 arr[현재 + i + 1]이 이미 방문했을때는 탐색해줄 필요가 없습니다.
• 3. 2*n개인 위치를 반복할때, 현재 + i +1 > 2n 이면 탐색해줄 필요가 없습니다.

아래는 정답코드입니다. 위 조건 3개를 충족시키게 구현했습니다.

#include <iostream>
using namespace std;
int n, x, y;
int arr[26] = { 0, };
bool checked[25] = { 0, };
int result = 0;

void dfs(int cur) {
	if (cur == n*2) {
		result++;
		return;
	}
	if (arr[cur] == 0) {

		for (int i = 1; i <= n; i++) {
			if (checked[i] == 0) {
				if (cur + i + 1 <= 2 * n && !arr[cur+i+1]) {
					checked[i] = 1;
					arr[cur] = i;
					arr[cur + i + 1] = i;
					dfs(cur + 1);
					checked[i] = 0;
					arr[cur] = 0;
					arr[cur + i + 1] = 0;
				}
			}
		}
	}
	else
		dfs(cur + 1);
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> x >> y;
	
	arr[y] = y - x - 1;
	arr[x] = y - x - 1;
	checked[y - x - 1] = 1;
	dfs(1);
	cout << result << endl;
	return 0;
}

문제링크: www.acmicpc.net/problem/20208

n*n은 100이므로 각각의 좌표를 전부 검사해주는 행동은 당연히 시간초과

"민트초코우유의 총합은 10개를 넘지 않는다." 라는 조건을 사용하여야 합니다. 즉, 각 좌표들의 거리로 탐색해야 합니다.

이때, 조합이 아니라 순열구조이므로 10! 만큼 소모될수 있습니다. 시간적으로 괜찮을 것을 확인했다면 

바로 구현하면 됩니다.

정답코드입니다.

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

typedef struct MyStruct
{
	int y;
	int x;
	bool checked;
}val;

int n = 0, m = 0, h = 0;
int result = 0;
int arr[10][10] = { 0, };
val house;
vector <val> mint;

void dfs(int y, int x,int cur, int cnt, int hp) {
	if (cnt > result) {// 방문횟수가 더 많고
		if (abs(y - house.y) + abs(x - house.x) <= hp)
			result = cnt;
	}
	if (hp <= 0)
		return;
	for (int i = 0; i < mint.size(); i++) {
		
			int len = abs(mint[i].y - y) + abs(mint[i].x - x);
			if (len <= hp && mint[i].checked == 0) {
				mint[i].checked = 1;
				dfs(mint[i].y, mint[i].x, i+1, cnt + 1, hp - len + h);
				mint[i].checked = 0;
			}
			
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> h;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++){
			int temp = 0;
			cin >> temp;
			if (temp == 1)
				house.y = i, house.x = j;
			else if (temp == 2)
				mint.push_back({ i,j,0 });
		}
	}
	
	dfs(house.y,house.x,0, 0, m);
	cout << result  << endl;
	return 0;
}

간혹 조합과 수열 구현을 헷갈려 하시는데, 아래 링크 참고하시면 좋을 것 같습니다. 

paris-in-the-rain.tistory.com/35

문제링크:www.acmicpc.net/problem/1941

백트래킹 문제입니다. 전체가 검색해주는 것이 아니라 임도연파 학생이 4이상이 될때 가지치기를 해주어야 합니다. (근데 제거 해주지 않아도 ac통과합니다.)

F 모양처럼 일반적인 방식의 dfs, bfs로는 구현할 수 없다는 것을 알게되었습니다.

모든 좌표를 탐색해야하는데 어떻게 구현할지 고민했습니다.

그리고 아래처럼 구현했습니다.

for (int i = y; i < 5; i++) {
		for (int j = (i == y ? x : 0); j < 5; j++) {
			if (chk[i][j] == 0) {
				chk[i][j] = 1;
				dfs(cnt + 1, i, j, arr[i][j] == 'S' ? som + 1 : som, arr[i][j] == 'Y' ? yim + 1 : yim);
				chk[i][j] = 0;
			}
		}
	}

y,x는 dfs에 넣어주는 값입니다. 모든 좌표중에 7개를 선택하는 경우입니다. 즉 25C7입니다.  480,700 가지의 경우의 수이므로 충분히 가능합니다. j = (i == y ? x : 0)는 처음에는 x좌표부터 시작하고 그이후점부터는 0으로 시작한다는 삼항연산자입니다.

• 1. 25개 좌표중에 7개 선택하기- dfs
• 2. 7개의 좌표들이 서로 연결되어 있는지 확인하기 - search
• 3. 결과도출

아래는 전체코드입니다.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int result = 0;
string arr[5];
bool chk[5][5] = { 0, };
bool temp[5][5] = { 0, };
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void search(int y, int x) {
	temp[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + y_ar[i];
		int nx = x + x_ar[i];
		if (chk[ny][nx] == 1 && temp[ny][nx] == 0)
			if (ny >= 0 && ny < 5 && nx >= 0 && nx < 5)
				search(ny, nx);
	}
}

void dfs(int cnt, int y, int x, int som, int yim) {
	if (yim >= 4)
		return;
	if (cnt == 7 && som >= 4) {
		int val_temp = 0;
		memset(temp, 0, sizeof(temp));
		for(int i=0;i<5;i++)
			for(int j=0; j<5;j++)
				if (chk[i][j] == 1&& temp[i][j]==0) {
					search(i, j);
					val_temp++;
				}

		if (val_temp == 1)
			result++;
		return;
	}


	for (int i = y; i < 5; i++) {
		for (int j = (i == y ? x : 0); j < 5; j++) {
			if (chk[i][j] == 0) {
				chk[i][j] = 1;
				dfs(cnt + 1, i, j, arr[i][j] == 'S' ? som + 1 : som, arr[i][j] == 'Y' ? yim + 1 : yim);
				chk[i][j] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	for (int i = 0; i < 5; i++)
		cin >> arr[i];

	dfs(0, 0, 0, 0, 0);

	cout << result << endl;

	return 0;
}

문제풀이:programmers.co.kr/learn/courses/30/lessons/12952?language=cpp

n-queen 문제입니다.

아래 백준 문제와도 동일합니다.

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

gusdnr69.tistory.com/132

2차원배열이 아닌 1차원 배열로 구현할 수 있습니다.

1. row배열에 열값을 넣는다.

2. 넣으면 같은열에 있는 좌표가 있는지,

3. 대각선 상으로 일치하는 부분이 있는지 검사한다.

3가지 를 순서대로 구현해주면 되는 백트래킹 문제였습니다.

아래는 정답코드입니다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <cmath>
int N, result = 0;
int row[13] = { 0, }; //열값을 넣어줄 예정

bool checked(int r) {

	for (int i = 0; i < r; i++) {
		if (row[i] == row[r])
			return false;
		else if (abs(row[i] - row[r]) == r - i)
			return false;
	}
	return true;
}

void dfs(int r) {
	if (N == r) {
		result++;
		return;
	}

	for (int i = 0; i < N; i++) { //0열부터 n-1열까지 검사
		row[r] = i;
		if (checked(r)) {
			dfs(r + 1);
		}
		row[r] = 0;
	}
	return;
}

int solution(int n) {
	int answer = 0;
	N = n;
	dfs(0);
	answer = result;
	return answer;
}

문제링크:www.acmicpc.net/problem/1759

dfs문제입니다. 조건에 맞게 구현해주면 되는 간단한 문제였습니다.

주의할점은

• 1. 알파벳들을 정렬해주어야 한다는 것 
• 2. 모음 1자, 자음 2자 이상이어야 한다는 것

정답코드입니다.

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

int l, c;
string arr;
bool checked[17] = { 0, };

void dfs(int cnt, int current) {

	if (cnt == l) {

		int m=0, j=0;
		for (int i = 0; i < arr.size(); i++) {
			if (checked[i]) {
				if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
					m++;
				else
					j++;
			}
		}
		if (m >= 1 && j >= 2) {
			for (int i = 0; i < arr.size(); i++)
				if (checked[i])
					cout << arr[i];
			cout << endl;
		}
		return;
	}


	for (int i = current; i < arr.size(); i++) {
		if (checked[i] == 0) {
			checked[i] = 1;
			dfs(cnt + 1, i);
			checked[i] = 0;
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> l >> c;
	for (int i = 0; i < c; i++) {
		char temp;
		cin >> temp;
		arr += temp;
	}
	sort(arr.begin(), arr.end());
	//cout << arr << endl;
	dfs(0, 0);
	return 0;
}