코딩하는 두꺼비

www.acmicpc.net/problem/13549

그냥 단순한 bfs 문제인줄 알았지만 간선이 0인 경우를 고려해야 해서 까다로운 문제였다..

결국 해결 하지 못해 힌트를 보고 말아서 좀 아쉬운 문제였다..

참고: www.acmicpc.net/board/view/38887#comment-69010

위에서 나오듯이 

1. 다익스트라 알고리즘을 사용하는 법

2. 0-1 BFS: 간선이 0(순간이동)을 넣을 떄 큐의 맨 앞에 넣는 법

3. * 2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

위의 세가지 방법 중에 하나를 사용하는 되는 문제였고 난 덱을 사용해서 결국 2번 방법을 사용해 풀 수 있었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

deque<pair<int, int>> dq;
int visit[100001];
int n, k;

void bfs(int x) {
	visit[x] = 1;
	dq.push_back({ x, 0 });
	while (!dq.empty()) {
		int y = dq.front().first;
		int z = dq.front().second;
		dq.pop_front();
		if (y == k) {
			cout << z;
			return;
		}
		if (2 * y <= 100000 && visit[2 * y] == 0) {
			visit[2 * y] = 1;
			dq.push_front({ 2 * y , z});
		}
		if (y - 1 >= 0 && visit[y - 1] == 0) {
			visit[y - 1] = 1;
			dq.push_back({ y - 1, z+1 });
		}
		if (y + 1 <= 100000 && visit[y + 1] == 0) {
			visit[y + 1] = 1;
			dq.push_back({ y + 1, z+1 });
		}
	}
}

int main() {
	cin >> n >> k;
	bfs(n);
	return 0;
}

www.acmicpc.net/problem/1707

처음엔 그냥 두 개의 벡터를 만들어서 나누는 식으로 구현을 하려 했지만 실패했고 결국 답을 볼 수 밖에 없었다.

1. 큐와 간선 그래프 등을 포함해 모든 것을 테스트 케이스마다 초기화 해주기

2. 연결 그래프가 아닐 수도 있다는 것

이 두가지가 중요한 문제였다고 생각한다.

결국 푼 방법은 0, 1, 2 세가지의 종류로 정점들을 나눴고 이를 활용해서 풀 수 있었다.

참고: hugssy.tistory.com/231

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

bool c = true;
int k, v, e;
queue<int> q;
vector<int> edges[20001];
int visit[20001];

void bfs(int x) {
	q.push(x);
	visit[x] = 1;
	while (!q.empty()) {
		int y = q.front();
		q.pop();
		for (int i = 0; i < edges[y].size(); i++) {
			int z = edges[y][i];
			if (visit[z] != 0 && visit[y] == visit[z]) {
				c = false;
				return;
			}
			if (visit[z] > 0) {
				continue;
			}
			q.push(z);
			visit[z] = visit[y] % 2 + 1;
		}
	}
}

int main() {
	int a, b;
	cin >> k;
	while (k--) {
		cin >> v >> e;
		for (int i = 0; i < e; i++) {
			cin >> a >> b;
			edges[a].push_back(b);
			edges[b].push_back(a);
		}
		for (int i = 1; i <= v; i++) {
			if (visit[i] == 0) {
				bfs(i);
			}
			if (!c) {
				cout << "NO" << "\n";
				break;
			}
		}
		if (c) {
			cout << "YES" << "\n";
		}
		while (!q.empty()) {
			q.pop();
		}
		for (int i = 1; i <= v; i++) {
			visit[i] = 0;
			edges[i].clear();
		}
		c = true;
	}
	return 0;
}

www.acmicpc.net/problem/1967

하루 넘게 고민해서 겨우 푼 문제이다..

처음엔 단순히 2개의 간선을 가지는 노드들을 dfs 두번 보내서 각각의 간선 가중치의 합을 더하고 그 중 최댓값을 출력하게 풀려했는데 잘 안되었다.

반례를 보고 깨달았는데 이진 트리가 아니라서 간선이 한 방향에만 있는 경우, 여러개 있는 경우를 고려해주어야 했던 것이다.

그래서 런타임 에러 등을 통해 고생하다가 결국 풀 수 있었다.

1. 간선의 내용을 모두 받아오고 2개 이상의 간선을 가지는 노드를 따로 빼준다. (1은 초기 상태로 무조건 넣어줌)

2. 그렇게 구한 노드들을 모두 확인하는데, 각 노드의 아래에 있는 간선들의 합을 더해주되, 최댓값과 그 두번째 값을 저장하여 정답 벡터에 넣어준다.

3. 정답 벡터에 들어가 있는 값들 중 최댓값 출력

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

vector <pair<int, int>> v[10001];
vector<int> v2;
vector<int> ans;
int cnt[10001];
int x, n;

void dfs(int b, int c) {
	if (v[b].empty()) {
		x = max(x, c);
		return;
	}
	for (int j = 0; j < v[b].size(); j++) {
		c += v[b][j].second;
		dfs(v[b][j].first, c);
		c -= v[b][j].second;
	}

}

int main() {
	int a, b, c;
	cin >> n;
	if (n == 1) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < n-1; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		cnt[a]++;
	}
	v2.push_back(1);
	for (int i = 2; i <= n; i++) {
		if (cnt[i] > 1) {
			v2.push_back(i);
		}
	}
	for (int i = 0; i < v2.size(); i++) {
		int res = 0;
		int m1 = 0, m2 = 0;
		for (int j = 0; j < v[v2[i]].size(); j++) {
			dfs(v[v2[i]][j].first, v[v2[i]][j].second);
			m2 = max(m2, min(m1,x));
			m1 = max(m1, x);
			x = 0;
		}
		ans.push_back(m1+m2);
	}
	cout << *max_element(ans.begin(), ans.end());
	return 0;
}