이것 저것 &

문제링크: 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;
}

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

간단한 dfs 문제였습니다. 

백트래킹의 요소는 잘 모르겠습니다. 단지 가까운 치킨 가게를 찾을때 bfs 탐색의 개념을 사용하지 말고, 각각의 치킨집과 집의 거리를  |r1-r2| + |c1-c2| 공식을 통해서 찾아주게끔만 구현해주면 맞는 간단한 문제입니다.

저는 치킨집 좌표를 구조체 벡터를 사용해서, 집 좌표는 pair사용해서 구현했습니다. 

아래는 정답 코드입니다. 

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

typedef struct a{
	int y;
	int x;
	bool checked;
}Chk;

vector <pair <int, int>> house;
vector <Chk> chicken;
int n = 0, m = 0;
int result = 2e9;

void dfs(int cnt, int current) {

	if (cnt == m) {
		/*
		for (int i = 0; i < chicken.size(); i++) {
			if (chicken[i].checked == true)
				cout << i << ' ';
		}
		cout << endl;*/

		int sum = 0;

		for (int i = 0; i < house.size(); i++) {
			int mined = 1000000000;
			for (int j = 0; j < chicken.size(); j++) {
				if (chicken[j].checked == false) continue;

				mined = min(mined, abs(house[i].first - chicken[j].y) + abs(house[i].second - chicken[j].x));
			}
			sum += mined;
		}

		if (result > sum)
			result = sum;

		return;
	}
	

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	// 1.
	cin >> n >> m;
	int num = 0;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			cin >> num;
			if (num == 1)
				house.push_back(make_pair(i, j));
			else if (num == 2)
				chicken.push_back({ i,j,0 });
		}
	//2.
	dfs(0, 0);

	cout << result << endl;
	return 0;
}

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

에라토스 체 알고리즘을 사용하면 n=8일때 시간초과가 일어납니다.

오히려 체알고리즘을 사용하지 않고 문제 조건 처럼  왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수인지

순서대로 찾아주는 것이 효율적입니다.

이를 재귀함수를 통해서 구현했습니다.

• 1. 첫수를 항상 2,3,5,7로 시작한다.
• 2. 그 이후 숫자는 반복문을 통해서 소수인지 확인하며 진행한다. 
• 3. 재귀함수가 n번 탐색했다면 해당 수는 소수이므로 바로 출력한다.

아래는 정답 코드입니다.

#include <iostream>
using namespace std;

int n = 0;

bool checked(int num) {

	for (int i = 2; i*i <= num; i++) {
		if (num%i == 0)
			return false;
	}
	return true;
}

void dfs(int num, int len) {
	if (len == n) {
		cout << num << "\n";
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (checked(num * 10 + i))
			dfs(num * 10 + i, len + 1);
	}

	return;
}

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

	
	cin >> n;
	dfs(2, 1);
	dfs(3, 1);
	dfs(5, 1);
	dfs(7, 1);
	return 0;
}

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

dfs 문제였습니다.

이때 완전탐색 횟수를 줄이는게 핵심인 문제였습니다.

우선 첫번째 코드를 먼저 보시죠.

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

int n = 0, m = 0;
int cost[100001] = { 0, };
vector <int> vec[100001];
int h, w;

void dfs(int current) {

	cost[current] += w;
	for (int i = 0; i < vec[current].size(); i++) {
		dfs(vec[current][i]);
	}
}

int main() {

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int temp;
		cin >> temp;
		if (i == 1) continue;
		vec[temp].push_back(i);
	}

		
	for (int i = 1; i <= m; i++) {
		cin >> h >> w;
		dfs(h);
	}

	for (int i = 1; i <= n; i++) {
		cout << cost[i];
		if (i == n)
			break;
		cout << ' ';
	}
	cout << '\n';

	return 0;
}

일반적으로 생각할 수 있는 방법입니다. 

근데 이렇게 제출하면 당연히 시간 초과가 납니다. 

좀더 효율적으로 탐색할 수 없을까 고민을 하던중에 

dfs를 한번만 돌아도 되는 아이디어를 생각했습니다.

아래처럼 dfs(1)을 호출하고 줄줄이 이전 cost값을 더해주는 형태로 구현했습니다. 

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

int n = 0, m = 0;
int cost[100001] = { 0, };
vector <int> vec[100001];
int h, w;

void dfs(int current) {

	for (int i = 0; i < vec[current].size(); i++) {
		cost[vec[current][i]] += cost[current];
		dfs(vec[current][i]);
	}
}

int main() {

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int temp;
		cin >> temp;
		if (i == 1) continue;
		vec[temp].push_back(i);
	}

		
	for (int i = 1; i <= m; i++) {
		cin >> h >> w;
		cost[h] += w;
	}
	dfs(1);
	for (int i = 1; i <= n; i++) {
		cout << cost[i];
		if (i == n)
			break;
		cout << ' ';
	}
	cout << '\n';

	return 0;
}

문제링크:https://www.acmicpc.net/problem/2580

일반적인 방법으로 풀면은 시간초과입니다.

dfs를 사용하고 이미 확인한 값에 대해서는 탐색하지 않는 백트래킹 기법을 사용해야 하는 어려운 문제였습니다.

이문제에서의 핵심은

bool row[9][10] = { 0 };
bool col[9][10] = { 0 };
bool square[9][10] = { 0 };

 세가지 방문여부입니다. row는 해당 행에서 수를 탐색했는지 여부, col은 열에서 수를 탐색했는지 여부, square는 속하는 3x3에서 수를 탐색했는지 여부를 판단합니다.

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];



			if (arr[i][j] != 0)
			{
				row[i][arr[i][j]] = true;
				col[j][arr[i][j]] = true;
				square[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
			}


		}

	dfs(0);



}

위 처럼 수를 입력받으면 row, col, square에 방문 수를 저장합니다. 

row[i][j] 라면 i행에서 j값을 방문했는지 여부를 표시합니다 즉 row[1][9]= true 면은 1행에 9는 존재한다는 의미입니다.

col과 square 모두 같은 맥락입니다.

이때 스퀘어는 

위와 같은 구조로 진행됩니다. (출처: 얍문님 티스토리)  

그렇기 때문에 (y/3)*3 + x/3 을 통해서 해당 위치에 표시하는 것입니다.

정답코드입니다. cnt값을 올려주며 진행하게 됩니다. 81일때에는 모든 값들이 채워져 있는 것이기에 종료하게 됩니다.

이때 exit(0)를 이용해서 바로 프로세스를 종료해버리면 시간을 단축시킵니다. 천천히 이해해보세요.

#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;

int arr[9][9] = { 0 };
bool row[9][10] = { 0 };
bool col[9][10] = { 0 };
bool square[9][10] = { 0 };




void dfs(int cnt) {

	if (cnt == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << arr[i][j] << ' ';
			cout << endl;
		}
		exit(0);
	}
	int y = cnt / 9;
	int x = cnt % 9;

	if (arr[y][x] != 0)
		dfs(cnt + 1);
	else {
		
		for (int i = 1; i <= 9; i++) {
			if (row[y][i] == 0 && col[x][i] == 0 && square[(y / 3) * 3 + (x / 3)][i] == 0) {
				row[y][i] = 1;
				col[x][i] = 1;
				square[(y / 3) * 3 + (x / 3)][i] = 1;

				arr[y][x] = i;
				dfs(cnt + 1);
				arr[y][x] = 0;

				row[y][i] = 0;
				col[x][i] = 0;
				square[(y / 3) * 3 + (x / 3)][i] = 0;

			}

		}

	}


	return;
	
}


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];



			if (arr[i][j] != 0)
			{
				row[i][arr[i][j]] = true;
				col[j][arr[i][j]] = true;
				square[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
			}


		}

	dfs(0);



}