[21.08.02] 재귀함수2/ 백트래킹

- 백트래킹 -> 가지치기

- 완전탐색(브루트포스) -> for문/ 재귀 

- DFS -> 그래프탐색

 

//--------------------0802 - 백트래킹

//5국가 중 3국가 중복없이 선택(JKB != JBK) -> 조합
#include <iostream>
#include <string.h>
#include <cstring>
using namespace std;

char a[6] = "JKBSC";
char path[10];
int used[4];

void abc(int level, int st) {
	if (level == 3) {
		cout << path << endl;
		return;
	}

	for (int i = st; i < 5; i < i++) {
		if (used[i] == 1) continue;
		used[i] = 1;
		path[level] = a[i];
		abc(level + 1, i+1);
		used[i] = 0;
	}
	
}

int main() {
	
	abc(0,0);

	return 0;
}

//올림픽 금은동 J가 무조건 금 중복x // JKB != JBK -> 순열
#include <iostream>
#include <string.h>
#include <cstring>
using namespace std;

char a[5] = "JKBS";
char path[10];
int used[4];

void abc(int level) {
	if (level == 3) {
		if (path[0] == 'J')
			cout << path << endl;
		return;
	}

	for (int i = 0; i < 4; i < i++) {
		if (used[i] == 1) continue;
		used[i] = 1;
		path[level] = a[i];
		abc(level + 1);
		used[i] = 0;
	}

}

int main() {

	abc(0);

	return 0;
}

//h세로, w가로 - 각 세로라인에서 값 하나씩 선택(같은 세로라인 선택금지) 최소값 구하기
//4 4
//3 5 6 3
//1 -3 -6 1
//5 -7 -6 5
//1 1 5 4
 
#include <iostream>
using namespace std;

int w;
int h;
int map[10][10];
int mini = 21e8;
int used[10];

void run(int lev, int sum)
{
	if (lev == h) {
		if (sum < mini) mini = sum;

		if (sum == -9) {
			int d = 1;
		}
		return;
	}

	for (int i = 0; i < w; i++) {
		if (used[i] == 1) continue;
		used[i] = 1;
		run(lev + 1, sum + map[lev][i]);
		used[i] = 0;
	}

}

int main()
{
	freopen_s(new FILE *, "Text.txt", "r", stdin);
	cin >> h >> w;

	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			cin >> map[y][x];
		}
	}
	run(0, 0);
	cout << mini;

	return 0;
}


//n개의 좌표입력받아 *3 *2 *1하였을때 최대, 최소 구하기-------ⓗ
#include <iostream>
using namespace std;

int map[3][4] = {
	1, 2, 3, 4,
	5,4, -1, -2,
	-3, 0, 1, 2
};

int n = 3;
int used[3][4];

int maxi = -21e8;
int mini = 21e8;

void run(int lev, int sum)
{
	if (lev == n) {

		if (sum > maxi) maxi = sum;
		if (sum < mini) mini = sum;

		return;
	}

	for (int y = 0; y < 3; y++) {
		for (int x = 0; x < 4; x++) {
			if (used[y][x] == 1) continue;
			used[y][x] = 1;
			run(lev + 1, sum + (n - lev) * map[y][x]);
			used[y][x] = 0;
		}
	}

}

int main()
{
	//n 곳을 선택
	//같은 좌표 중복 선택 불가
	//3배, 2배, 1배 가중치 값 존재
	//합의 최댓값과 최솟값 둘다 출력하기

	run(0, 0);

	cout << maxi << endl;
	cout << mini << endl;

	return 0;
}

//direct 사용하여 대각선방향 합의 최대 구하기
#include <iostream>
using namespace std;

int map[5][6] = {
	1, 0, 2, 1, 2, 1,
	-1, 0, 1, 1, 2, 2,
	3, 3, 1, 2, 3, 4,
	5, 5, 5 ,3, 1, 2,
	1, 2, 3, 4, 0, 0
};

int directY[5] = { -1, -1, 1, 1, 0 };
int directX[5] = { -1, 1, -1, 1, 0 };

int getNum(int y, int x)
{
	int sum = 0;
	for (int t = 0; t < 5; t++) {
		int ny = y + directY[t];
		int nx = x + directX[t];
		if (ny < 0 || nx < 0 || ny >= 5 || nx >= 6) continue;
		sum += map[ny][nx];
	}
	return sum;
}

int main()
{
	//세 좌표를 입력받고
	//다섯 곳의 합을 구하는데
	//세 곳중 MAX값 출력

	int maxi = -21e8; //-21억
	for (int t = 0; t<3; t++) {
		int y, x;
		cin >> y >> x;

		int ret = getNum(y, x);
		if (maxi < ret) maxi = ret;

	}
	cout << maxi;

	return 0;
}


//배열에서 중복없이 세가지수 조합 -------------------->중요★
//2.재귀사용
#include <iostream>
#include <vector>
using namespace std;

vector<int> v = { 4, 5, 1, 7, 9, 2, 6 };
char path[10];

void run(int lev, int start)
{
	if (lev == 3) {
		cout << path << endl;
		return;
	}

	for (int i = start; i < v.size(); i++) {
		path[lev] = v[i] + '0';
		run(lev + 1, i + 1);
	}
}

int main()
{
	run(0, 0);

	return 0;
}

//1. 3중 for문 사용
#include <iostream>
#include <vector>
using namespace std;

vector<int> v = { 4, 5, 1, 7, 9, 2, 6 };

int main()
{
	for (int a = 0; a < v.size(); a++) {
		for (int b = a + 1; b < v.size(); b++) {
			for (int c = b + 1; c < v.size(); c++) {
				cout << v[a] << v[b] << v[c] << endl;
			}
		}
	}

	return 0;
}
 

// 백트래킹을 이용한 미로찾기------>추후 다시 다룰예정
#include <iostream>
#include <Windows.h>
using namespace std;

int map[8][8] = {
	0,1,0,0,1,0,0,0,
	0,1,0,0,0,0,1,0,
	0,0,0,0,1,1,1,0,
	0,1,1,0,1,0,1,0,
	0,1,0,0,0,0,1,0,
	0,0,0,0,1,1,0,0,
	0,1,1,0,1,1,0,1,
	0,1,1,0,1,0,0,0,
};

int used[8][8];
int direct[4][2] = { -1, 0, 1, 0, 0, 1, 0, -1 };

void print(int nowY, int nowX)
{
	system("cls");
	for (int x = 0; x < 10; x++) cout << "■";
	cout << endl;
	for (int y = 0; y < 8; y++) {
		cout << "■";
		for (int x = 0; x < 8; x++) {
			if (y == nowY && x == nowX) {
				cout << "★";
			}
			else if (map[y][x] == 0) {
				cout << "  ";
			}
			else {
				cout << "■";
			}
		}
		cout << "■";
		cout << endl;
	}
	for (int x = 0; x < 10; x++) cout << "■";
	Sleep(50);
}

void run(int nowY, int nowX)
{
	print(nowY, nowX);
	if (nowY == 7 && nowX == 7) {
		cout << "발견" << endl;
		system("color 1F");
		Sleep(1000);
		system("color 07");
		return;
	}

	for (int t = 0; t < 4; t++) {
		int ny = nowY + direct[t][0];
		int nx = nowX + direct[t][1];

		if (ny < 0 || nx < 0 || ny >= 8 || nx >= 8) continue;
		if (map[ny][nx] == 1) continue;
		if (used[ny][nx] == 1) continue;
		used[ny][nx] = 1;
		run(ny, nx);
		print(nowY, nowX);
		used[ny][nx] = 0;
	}

}

int main()
{
	used[0][0] = 1;
	run(0, 0);

	return 0;
}

//ABCD친구들이 영화관가는 경우의수 0~ABCD
#include<iostream>
using namespace std;
char path[10];
char name[3] = "ox";
char fri[5] = { "ABCD" };
void abc(int level)
{
	if (level == 4)
	{
		for (int x = 0; x < level; x++)
		{
			if (path[x] == 'o')cout << fri[x];
		}
		cout << endl;
		return;
	}
	for (int x = 0; x < 2; x++)
	{
		path[level] = name[x];
		abc(level + 1);
		path[level] = 0;
	}
}
int main()
{
	abc(0);
	return 0;
}

//A~입력받은 알파벳까지 중복제외 조합 모두출력 (AB 또는 BA처럼 연달아 출력 금지)
#include<iostream>
using namespace std;

char path[10];
char ch;
int used[100];

int abs(int v)
{
	if (v < 0) return -v;
	return v;
}

void run(int lev)
{
	if (lev >= 2 && abs(path[lev - 2] - path[lev - 1]) <= 1) return;

	if (ch - 'A' + 1 == lev) {
		cout << path << endl;
		return;
	}

	for (char c = 'A'; c <= ch; c++) {
		if (used[c] == 1) continue;
		used[c] = 1;
		path[lev] = c;
		run(lev + 1);
		used[c] = 0;
	}
}

int main()
{
	cin >> ch;

	run(0);

	return 0;
}

//설계후 구현하기 - 2차원 배열의 왼쪽과 위 비교후 작은값의 +3해서 완성하기
#include<iostream>
using namespace std;

int arr[4][6] = {
	{5,8,3,2,6,5},
	{4,0,0,0,0,0},
	{2,0,0,0,0,0},
	{6,0,0,0,0,0}, };

int main()
{

	for (int i = 1; i < 4; i++) {
		for (int j = 0; j < 5; j++) {
			if (arr[i][j] > arr[i - 1][j + 1])
				arr[i][j + 1] = arr[i - 1][j + 1] + 3;
			else {
				arr[i][j + 1] = arr[i][j] + 3;
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 6; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

//숫자카드에서 이웃하는 카드의 합 15미만
#include<iostream>
using namespace std;

int nums[5] = { 11, 5, 7, 4, 9 };
int path[10];

void run(int lev)
{
    if (lev >= 2 && path[lev - 2] + path[lev - 1] >= 15) return;

    if (lev == 4) {
        for (int i = 0; i < lev; i++) {
            cout << path[i] << " ";
        }
        //cout << endl;
        cout << "\n";
        return;
    }

    for (int i = 0; i < 5; i++) {
        //if (lev >= 1 && path[lev - 1] + nums[i] >= 15) continue;
        path[lev] = nums[i];
        run(lev + 1);
        path[lev] = 0; //옵션
    }
}


int main()
{
    run(0);
    

    return 0;
}

//n개의 주사위 합 10 이하인경우만 0+0+0=0 출력
#include<iostream>
using namespace std;

int n = 3;
char vect[10];

void run(int lev, int sum)
{
	if (sum > 10) return;

	if (lev == n) {
		int i = 0;
		for (i = 0; i < n - 1; i++) {
			cout << vect[i] << " + ";
		}
		cout << vect[i];
		cout << " = " << sum;
		cout << endl;
		return;
	}

	for (int i = 1; i <= 6; i++) {
		vect[lev] = '0' + i;
		run(lev + 1, sum + i);
	}

}

int main()
{
	run(0, 0);


	return 0;
}