이것 저것 &

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

트리에서 가장 긴구간을 구하기 위해서는 

• 1. 한점에서 가장 먼 점을 찾는다.
• 2. 해당 점에서 가장 멀리 갈 수 있는 거리를 구한다.

두가지를 순서대로 구현해주면 됩니다.

저는 이전에 유사한 문제를 풀어봐서 쉽게 풀었네요.

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

int v = 0;
vector <pair<int, int>> vec[100001];
int far = 0, far_val = 0;
bool visited[100001];


void dfs(int current, int sum) {
	if (sum > far_val) {
		far = current;
		far_val = sum;
	}

	for (int i = 0; i < vec[current].size(); i++) {
		int num = vec[current][i].first;
		if (visited[num] == 0) {
			visited[num] = 1;
			dfs(num, sum + vec[current][i].second);
		}
	}


}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	//input
	cin >> v;
	for (int i = 1; i <= v; i++) { // 간선 개수만큼 반복
		int a = 0;
		cin >> a;
		int b = 0, bval = 0;
		while (1) {
			cin >> b;
			if (b == -1)
				break;
			cin >> bval;
			vec[a].push_back(make_pair(b, bval));
			vec[b].push_back(make_pair(a, bval));

		}
	}

	//1. 가장 먼 곳 찾기
	memset(visited, 0, sizeof(visited));
	visited[1] = 1;
	dfs(1, 0);
	//cout << "far " << far << endl;
	
	//2. 결과 도출하기
	int f = far;
	far = 0, far_val = 0;
	memset(visited, 0, sizeof(visited));
	visited[f] = 1;
	dfs(f, 0);

	cout << far_val << endl;
	return 0;
}

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

대부분

• 순간 이동(0초 소요)은 걷는 이동(1초 소요)보다 더 빠르기때문에, 우선 순위가 높다. 

라는 조건을 생각해서 deque나 우선순위 큐를 사용해서 구현하셨더군요!

저는 일반 큐를 사용해서 구현했습니다. (수가 100,000까지 이기때문에 모든 방문노드를 들러도 된다고 인지했습니다. )

아래는 정답코드입니다.

천천히 확인해보세요.

#include <iostream>
#include <queue>
using namespace std;
int n = 0, k = 0;
int visited[100001] = { 0, };


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	queue <int> que;


	cin >> n >> k;
	que.push(n);
	visited[n] = 1;

	while (!que.empty()) {
		
		int v = que.front();
		que.pop();
		//cout << v << endl;
		for (int j = v; j <= 100000; j *= 2) { // 0초 후에 2*X의 위치로 이동
			if (j == 0) break;
			if (visited[j] == 0) {
				visited[j] = visited[v];
				que.push(j);
			}
		}
		if (visited[v + 1] == 0 && (v+1) <= 100000) {
			visited[v + 1] = visited[v] + 1;
			que.push(v + 1);
		}
		if (visited[v - 1] == 0 && (v-1) >= 0) {
			visited[v - 1] = visited[v] + 1;
			que.push(v - 1);
		}



	}

	cout << visited[k] - 1 << endl;
	return 0;
}

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

문제풀이를 위해선 

1.가장 깊은 노드 중 가중치가 가장 큰 노드를 찾는다.

2. 찾은 노드를 기준 정점으로 잡고, 다시 한번 가장 가중치가 큰 노드를 찾는다.

2가지를 수행하면 된다.

왜 이렇게 되는지에 대한 증명은 구사과님 글을 참고하자.

koosaga.com/14

구현난이도는 쉽지만 아이디어 캐치가 어려운 문제였다.

이래서 개발자는 수학베이스가 있어야 하는것인가..

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

int n = 0;
bool visited[10001] = { 0, };
vector <pair<int, int>> arr[10001];

int result = 0;
int destination = 0;

void dfs(int cur, int len) {

	if (result < len) {
		result = len;
		destination = cur;
	}

	for (int i = 0; i < arr[cur].size(); i++) {
		if (visited[arr[cur][i].first] == 0) {
			visited[arr[cur][i].first] = 1;
			dfs(arr[cur][i].first, len + arr[cur][i].second);
		}
	}


}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int s, e, v;
		cin >> s >> e >> v;
		arr[s].push_back(make_pair(e, v));
		arr[e].push_back(make_pair(s, v));
	}

	visited[1] = 1;
	dfs(1, 0); //목적지 구하고
	cout << result << endl;
	
	memset(visited, 0, sizeof(visited));
	result = 0;
	
	visited[destination] = 1;
	dfs(destination, 0);

	cout << result << endl;
	

}

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

dfs문제입니다. 

전형적인 dfs문제입니다. 백트래킹에 속하는 이유는 문제조건중에서

 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

라는 조건을 수행해야하기 때문입니다.

일반적인 dfs 방식을 사용해서 구현했습니다.

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t = 0, result = 0;
int arr[11][11] = { 0, };
bool visited[11];

void dfs(int cnt, int sum) {
	if (cnt == 11) {
		result = max(result, sum);
		return;
	}

	for (int i = 0; i < 11; i++) {
		if (arr[cnt][i] == 0)
			continue;
		if (visited[i] == 0) {
			visited[i] = 1;
			dfs(cnt + 1, sum + arr[cnt][i]);
			visited[i] = 0;
		}


	}
}

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

	cin >> t;

	while (t--) {
		for (int i = 0; i < 11; i++)
			for (int j = 0; j < 11; j++)
				cin >> arr[i][j];
		memset(visited, 0, sizeof(visited));
		result = 0;
		dfs(0, 0);
		cout << result << "\n";
	}

}

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

문제 조건에 따르며 구현했습니다.

두 동전의 좌표는 각각 c1y(coin 1 y좌표), c2x( coin 2 x 좌표)와 같은 형태로 나타냈습니다.

신경써야할 조건은 아래와 같습니다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
• 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1

조건에 맞추어 구현해주면 되는 dfs 겸 시뮬레이션 문제였습니다. 

아래는 정답코드입니다. 

1. 코인 두개 모두 범위안에 존재

2. 코인 둘 다 범위밖에 존재

3. 두개의 코인 중 하나만 밖으로 나감(결과 도출)

#include <iostream>
#include <string>
using namespace std;
int n, m;
int result = 2e9;
string arr[21]; //0base
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void dfs(int cnt, int c1y, int c1x, int c2y, int c2x) {
	
	if (cnt == 10)
		return;

	for (int i = 0; i < 4; i++) {
		int n1y = c1y + y_ar[i];
		int n1x = c1x + x_ar[i];
		int n2y = c2y + y_ar[i];
		int n2x = c2x + x_ar[i];
		if (n1y >= 0 && n1y < n && n2y >= 0 && n2y < n && n1x >= 0 && n1x < m &&  n2x >= 0 && n2x < m) {
			if (arr[n1y][n1x] == '#' && arr[n2y][n2x] == '#')
				continue;
			if (arr[n1y][n1x] == '#')
				n1y = c1y, n1x = c1x;
			if (arr[n2y][n2x] == '#')
				n2y = c1y, n2x = c1x;
			dfs(cnt + 1, n1y, n1x, n2y, n2x);
		}
		else if ((n1y < 0 || n1y >= n || n1x < 0 || n1x >= m) && (n2y < 0 || n2y >= n || n2x < 0 || n2x >= m)) {
			continue;
		}
		else {
			if (result > cnt + 1)
				result = cnt + 1;
			return;
		}
	}

}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int c1y, c1x, c2y, c2x;
	bool chk = false;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < m; j++)
			if (arr[i][j] == 'o'&& chk == false) {
				c1y = i, c1x = j;
				chk = true;
			}
			else if (arr[i][j] == 'o'&& chk == true) {
				c2y = i, c2x = j;
			}
	}
	dfs(0, c1y, c1x, c2y, c2x);
	if (result == 2e9)
		cout << -1 << endl;
	else
		cout << result << endl;
	return 0;
}

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