굳건하게

문제 : https://www.acmicpc.net/problem/2660

그래프 플로이드와샬

● 회장은 회원들 중에서 가장 점수가 작은 사람입니다.

● 회원의 점수는 다른 회원들까지의 거리(그래프 상의 경로의 길이) 중 가장 긴 값이 됩니다.

즉, 플로이드와샬 알고리즘을 통해 각 노드(회원) 별로 다른 모든 노드와의 거리를 구해서 그 중 가장 큰 값으로 회원의 점수를 지정하고, 각 회원별로 가장 작은 점수를 가진 사람들을 회장 후보로 올리면 됩니다.

#include<iostream>
#include<algorithm>

using namespace std;

const int INF = 9999999;
int N, x, y;
int map[51][51];
bool checkMinScore[51];
int minScore[51];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			map[i][j] = INF;
	for (int i = 1; i <= N; i++)
		map[i][i] = 0;

	while (1) {
		cin >> x >> y;
		if (x == -1 && y == -1)
			break;
		map[x][y] = map[y][x] = 1;
	}

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (map[i][k] + map[k][j] < map[i][j])
					map[i][j] = map[i][k] + map[k][j];

	int mm = INF;
	for (int i = 1; i <= N; i++) {
		int m = 0;
		for (int j = 1; j <= N; j++) {
			m = max(m, map[i][j]);
		}
		minScore[i] = m;
		mm = min(mm, minScore[i]);
	}

	int cnt = 0;
	for (int i = 1; i <= N; i++)
		if (minScore[i] == mm) {
			cnt++;
		}
	cout << mm << ' ' << cnt << '\n';
	for (int i = 1; i <= N; i++)
		if (minScore[i] == mm) {
			cout << i << ' ';
		}

	return 0;
}

문제 : https://www.acmicpc.net/problem/13549

BFS DP

 단순 BFS 탐색으로 문제를 해결하려하면, 순간이동을 하는 경우가 시간초가 0초 이므로 문제를 해결할 수 없습니다. 따라서, 순간이동을 하는 경우들을 먼저 큐에 push 해주는 방식으로 BFS 탐색을 진행하거나 혹은 BFS + DP 를 활용해서 문제를 해결 할 수 있습니다.

1) 순간이동을 먼저 push 해주는 방식의 BFS

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

bool visited[200000 + 1];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, K;
	cin >> N >> K;

	queue<pair<int, int>> q;
	q.push({ N, 0 });
	visited[N] = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();
		if (cur.first == K) {
			cout << cur.second << '\n';
			break;
		}
		if (0 <= cur.first - 1 && !visited[cur.first - 1]) {
			q.push({ cur.first - 1, cur.second + 1 });
			visited[cur.first - 1] = 1;
		}
		if (cur.first + 1 <= K && !visited[cur.first + 1]) {
			q.push({ cur.first + 1, cur.second + 1 });
			visited[cur.first + 1] = 1;
		}
		if (cur.first * 2 <= 200000 && !visited[cur.first * 2]) {
			q.push({ cur.first * 2, cur.second });
			visited[cur.first * 2] = 1;
		}
	}
	return 0;
}

2) 이동하거나 순간이동하거나 순서를 신경쓰지 않고 BFS + DP 활용

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

int visited[200000 + 1];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, K;
	cin >> N >> K;
	for (int i = 0; i < 200001; i++)
		visited[i] = 99999999;

	queue<pair<int, int>> q;
	q.push({ N, 0 });
	visited[N] = 0;
	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();
		if (cur.first == K) {
			cout << visited[K] << '\n';
			break;
		}
		if (cur.first * 2 <= 200000 && cur.second < visited[cur.first * 2]) {
			q.push({ cur.first * 2, cur.second });
			visited[cur.first * 2] = cur.second;
		}
		if (0 <= cur.first - 1 && cur.second + 1 < visited[cur.first - 1]) {
			q.push({ cur.first - 1, cur.second + 1 });
			visited[cur.first - 1] = cur.second + 1;
		}
		if (cur.first + 1 <= K && cur.second + 1 < visited[cur.first + 1]) {
			q.push({ cur.first + 1, cur.second + 1 });
			visited[cur.first + 1] = cur.second + 1;
		}
	}
	return 0;
}

문제 : https://www.acmicpc.net/problem/4485

BFS DP

 DP[i][j] := (N -1, N -1) 에서 ( i, j ) 까지 가는 가장 작은 비용.

 (N-1, N-1) 에서 (0, 0) 까지 경로를 탐색해나가며 DP 배열을 채워나가면 문제를 해결할 수 있다. 현재 내 위치 (curX, curY) 에서 다음 위치 (nX, nY)로 이동할 때, dp[curX][curY] + map[nX][nY] 보다 이미 dp[nX][nY]가 작다면 해당 경로는 탐색해도 의미가 없으므로 탐색을 진행하지 않고, dp[nX][nY] 보다 값이 작을 때만 계속 BFS 탐색을 진행해나간다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int round = 1;
	while(true){
		int N, map[125][125] = {}, dp[125][125] = {}, dx[4] = { 0, -1, 0, 1 }, dy[4] = { -1, 0, 1, 0 };
		cin >> N;
		if (N == 0)
			break;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++){
				cin >> map[i][j];
				dp[i][j] = 99999999;
			}

		queue<pair<int, int>> q;
		q.push({ N - 1, N - 1 });
		dp[N - 1][N - 1] = map[N - 1][N - 1];

		while (!q.empty()) {
			pair<int, int> cur = q.front(); q.pop();
			for (int i = 0; i < 4	; i++) {
				int nX = cur.first + dx[i], nY = cur.second + dy[i];
				if (0 <= nX && nX < N && 0 <= nY && nY < N && dp[cur.first][cur.second] + map[nX][nY] < dp[nX][nY]) {
					dp[nX][nY] = dp[cur.first][cur.second] + map[nX][nY];
					q.push({ nX, nY });
				}
			}
		}
		cout << "Problem " << round << ": " << dp[0][0] << '\n';
		round++;
	}
	return 0;
}

문제 : https://www.acmicpc.net/problem/16953

BFS

 A에서 BFS 탐색을 진행하면 되는데, 범위가 10^9로 check 배열을 따로 만들 수 없다. 하지만, 항상 증가하는 방향으로 숫자가 변하기 때문에 사이클이 생길 수 없으므로 그냥 BFS 탐색을 진행하면 된다.

#include<iostream>
#include<queue>

using namespace std;

long long A, B;
queue<pair<long long, int>> q;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> A >> B;

	q.push({ A, 0 });
	while (!q.empty()) {
		pair<long long, int> cur = q.front(); q.pop();
		if (cur.first == B) {
			cout << cur.second + 1 << '\n';
			return 0;
		}
		if (cur.first * 2 <= B){
			q.push({ cur.first * 2, cur.second + 1 });
		}
		if (cur.first * 10 + 1 <= B) {
			q.push({ cur.first * 10 + 1, cur.second + 1 });
		}
	}
	cout << -1;
	return 0;
}