이것 저것 &

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

너무나도 간단한 bfs 문제입니다.

숫자 범위가 크기 때문에 bfs를 선택했고, 방문여부를 판단하는 배열을 만들어서 문제를 해결했습니다.

아래는 정답 코드입니다.

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

int n = 0, k = 0;
int result = 0;
int visited[100001] = { 0, };
queue <int> que;

int main() {
	iostream::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;

	que.push(n);
	visited[n] = 1;
	while (!que.empty()) {
		int p = que.front();
		que.pop();
		if (p == k) {
			cout << visited[p] - 1 << endl;
			return 0;
		}
		if (visited[p - 1] == 0 && (p - 1) >= 0 && (p - 1) <= 100000)
			que.push(p - 1), visited[p - 1] = visited[p] + 1;
		if (visited[p + 1] == 0 && (p + 1) >= 0 && (p + 1) <= 100000)
			que.push(p + 1), visited[p + 1] = visited[p] + 1;
		if (visited[p*2] == 0 && (p*2) >= 0 && (p*2) <= 100000)
			que.push(p*2), visited[p*2] = visited[p] + 1;
	}

	return 0;
}

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

• '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
• 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
• 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

위

3가지 조건을 통해서 점화식을 도출해야 합니다.

문제 접근 방법:

1. 모든 경우의 수를 비교해주어야 하는 것을 인지

2. 수의 범위가 10000임으로 일반적인 dfs 를 쓰면 시간 초과가 남을 인지

3. dp방식을 통해서 한번 확인한 마을이라면 마킹을 해두며 진행해야함을 인지

점화식은 

일반 마을 = 인접 마을 중에서 최대값

우수 마을 = 인접 마을 중에서 일반 마을들의 최대값 

이고 up-down방식으로 구현했습니다.

아래는 정답 코드입니다.

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

int n = 0;
bool visited[10001] = { 0, };
int cost[10001] = { 0, };
vector <int> arr[10001];
int dp[10001][2];
void dfs(int current) {
	if (visited[current])
		return;
	
	visited[current] = 1;
	int& normal = dp[current][0];
	int& greated = dp[current][1];
	normal = 0;
	greated = cost[current];
	for (int i = 0; i < arr[current].size(); i++) {
		int num = arr[current][i];
		if (visited[num] == 1) continue;

		dfs(num);
		normal += max(dp[num][1], dp[num][0]);
		greated += dp[num][0];
		
	}
}



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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
	}

	for (int i = 0; i < n - 1; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		arr[t1].push_back(t2);
		arr[t2].push_back(t1);
	}

	dfs(1);

	cout << max(dp[1][0],dp[1][1]) << endl;

	return 0;
}

dfs를 먼저 호출하고 해당 값들에 넣어주어야지 값들이 올바르게 들어갑니다.

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

기본적인 bfs, dfs 문제입니다.

vector를 통해서 양방향 그래프를 구현하고 완전탐색을 통해서 연결된 갯수를 파악하면 되는 문제입니다.

기본중에 기본문제입니다. 

이제 알고리즘을 입문하시는 분들이라면 그냥 코드자체를 외우듯이 이해하시면 될 것 같습니다.

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

int n = 0, m = 0, result = 0;
vector <int> vec[101];
bool visited[101] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		vec[t1].push_back(t2);
		vec[t2].push_back(t1);

	}

	queue <int> que;
	visited[1] = 1;
	que.push(1);

	while (!que.empty()) {
		int num = que.front();
		que.pop();

		for (int i = 0; i < vec[num].size(); i++) {
			int next = vec[num][i];
			if (visited[next] == 1) continue;
			que.push(next);
			visited[next] = 1;
			result++;
		}
	}

	cout << result << 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;
}