굳건하게

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

[ 주접주접 ]

 단순 BFS 문제 같은데 왜이렇게 정답률이 극악인가했더니,,, 문제를 완벽하게 이해하기가 참 어렵고 숨겨진 조건이 많아서 결국 2번 틀리고 Solve를 받았다.

[ 알고리즘풀이 ]

● 견우는 오작교를 연속해서 건널 수 없다! 즉, 오작교가 2개가 연달아있으면 연달아 오작교를 이용할 수 없다.

● 주기가 M인 오작교는 내가 M - 1 시점에 오작교 옆에 땅이여야 M 시점에 오작교로 이동이 가능하다.

● 먼저 오작교를 세울 수 있는 절벽인지 아닌지 판단한 후 세울 수 있다면 bridge에 좌표를 다 담는다.

( 이때, 오작교를 세울 수 있는지 없는지는 왼쪽 + 위 / 위 + 오른쪽 / 오른쪽 + 아래 / 아래 + 왼쪽 이 동시에 절벽인지 아닌지 체크해주면 된다. )

● 오작교를 세우지 않고 BFS 탐색을 진행하고, 그 후 오작교를 세울 수 있는 절벽마다 주기가 M인 오작교를 세운 후 BFS 탐색을 진행한다.

● BFS 탐색은 총 4가지 값들을 queue에 담으면서 진행하는데 << x좌표, y좌표 >, <현재시간, 오작교밟았는지여부>> 를 통해 내가 다음에 밟아야할 좌표가 일반적인땅(1) 이라면 그냥 queue에 <<다음에밟아야할좌표>, <현재시간+1, 0>> 을 push 해주고, 오작교라면 오작교 주기와 맞아떨어져서 밟을 수 있고, 기존에 오작교를 밟지 않았다면 오작교로 이동을 하고, 오작교 주기와 맞아떨어지지않지만 기존에 오작교를 밟지 않았다면 현재 자리에서 대기를 해야되므로 현재 자리를 다시 push 해준다.

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

int N, M, map[10][10], ans = 99999;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };

bool checkBound(int i, int j) {
	if (0 <= i && i < N && 0 <= j && j < N)
		return true;
	return false;
}

bool checkBridge(int i, int j) {
	if (checkBound(i, j - 1) && checkBound(i - 1, j) && map[i][j - 1] == 0 && map[i - 1][j] == 0)
		return false;
	if (checkBound(i - 1, j) && checkBound(i, j + 1) && map[i - 1][j] == 0 && map[i][j + 1] == 0)
		return false;
	if (checkBound(i, j + 1) && checkBound(i + 1, j) && map[i][j + 1] == 0 && map[i + 1][j] == 0)
		return false;
	if (checkBound(i + 1, j) && checkBound(i, j - 1) && map[i + 1][j] == 0 && map[i][j - 1] == 0)
		return false;
	return true;
}

void BFS(void) {
	bool visited[10][10] = {};
	queue<pair<pair<int, int>,pair<int, int>>> q;
	q.push({ {0, 0}, {0, 0} });
	visited[0][0] = 1;

	while (!q.empty()) {
		pair<pair<int, int>,pair<int, int>> cur = q.front();
		q.pop();
		pair<int, int> curP = cur.first;
		int time = cur.second.first;
		int flag = cur.second.second;

		if (curP == make_pair(N - 1, N - 1)) {
			ans = min(ans, time);
			break;
		}

		for (int i = 0; i < 4; i++) {
			int nX = curP.first + dx[i], nY = curP.second + dy[i];
			if (!checkBound(nX, nY))
				continue;

			if (map[nX][nY] == 1 && !visited[nX][nY]) { // 그냥 갈 수 있는 땅
				q.push({ {nX,nY}, {time + 1, 0} });
				visited[nX][nY] = 1;
			}

			if (map[nX][nY] >= 2 && !visited[nX][nY] && !flag) { // 오작교가 있고 전에 오작교를 밟지 않음.
				if ((time + 1) % map[nX][nY] == 0) { // 오작교를 갈 수 있다.
					visited[nX][nY] = 1;
					q.push({ {nX, nY}, {time + 1, 1} });
				}
				else { // 제자리 대기
					q.push({ {curP.first, curP.second}, {time + 1, 0} });
				}
			}
		}
	}
}

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

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

	vector<pair<int, int>> bridge;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0 && checkBridge(i, j)) {
				bridge.push_back({ i, j });
			}
		}
	}
	
	BFS();
	for (int i = 0; i < bridge.size(); i++) {
		map[bridge[i].first][bridge[i].second] = M;
		BFS();
		map[bridge[i].first][bridge[i].second] = 0;
	}

	cout << ans << '\n';

	return 0;
}

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

[ 알고리즘풀이 ]

 Union-Find 와 자료구조 Map을 이용하면 문제를 해결할 수 있습니다. 이름이 Input 으로 들어오면, Map에 없다면 <이름, 번호>를 Map에 Insert 해주고 이 번호를 이용해 Union-Find를 하면 된다. 집합의 크기를 출력해줘야되므로, 그냥 유파가 아닌 WeightedUnion-Find 기법을 활용했다.

#include<iostream>
#include<map>
#include<string>
#include<cstring>

using namespace std;

int p[100000];

int find(int num) {
	if (p[num] < 0)
		return num;
	return p[num] = find(p[num]);
}

void merge(int num1, int num2) {
	int pNum1 = find(num1), pNum2 = find(num2);
	if (pNum1 == pNum2)
		return;

	if (p[pNum1] < p[pNum2]) { // i 가 더 많음.
		p[pNum1] = p[pNum1] + p[pNum2];
		p[pNum2] = pNum1;
	}
	else{
		p[pNum2] = p[pNum1] + p[pNum2];
		p[pNum1] = pNum2;
	}
	return;
}

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

	int t;
	cin >> t;
	while (t--) {
		memset(p, -1, sizeof(p));

		int F;
		cin >> F;
		int count = 0;
		map<string, int> list;
		string input1, input2;
		for (int i = 0; i < F; i++) {
			cin >> input1 >> input2;
			if (list.count(input1) == 0) {
				list.insert({ input1, count });
				count++;
			}
			if (list.count(input2) == 0) {
				list.insert({ input2, count });
				count++;
			}
			merge(list.find(input1)->second, list.find(input2)->second);
			cout << -p[find(list.find(input1)->second)] << '\n';
		}
	}
	return 0;
}

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

[ 주접주접 ]

 처음에는 DFS 탐색을 통해서 startNode에서 시작해서 탐색을 진행하며 경로 중 가장 작은 cost를 매개변수로 넘겨주며 endNode까지 탐색이 끝나면 답을 갱신하는 방법으로 알고리즘을 구현했다. 당연히, 시간 초과에 직면했고 그 후 갱신된 답보다 작거나 같은 경우에는 탐색을 중간에 종료하며 DFS 컷팅을 시도했으나 이 알고리즘도 시간 초과에 직면했다... 그러다 Union-Find 기법으로 문제를 해결할 수 있다는 글을 보았고 Union-Find로 A노드에서 B노드로 경로가 있는지 없는지 바로 체크할 수 있다는 점을 이용해서 문제를 해결했다.

[ 알고리즘풀이 ]

 우리는 startNode에서 endNode로 경로를 만들면되는데, 어차피 cost가 작은 간선보다는 cost가 큰 간선들로 경로를 만들고 싶다. 따라서, cost가 큰 간선부터 탐색하며 startNode와 endNode 가 경로가 생긴 순간 탐색을 종료하면 된다. 이때, startNode와 endNode가 경로가 생겼는지 안생겼는지는 Union-Find를 이용해서 쉽게 해결할 수 있다.

[ 예시 ]

1)

 cost가 가장 큰 간선 4 - 5 를 가지고와 4와 5를 Merge 합니다. 즉, 4번 5번 노드 사이에는 경로가 존재합니다. { 4, 5 }

2)

 다음으로 큰 간선인 5 - 6 을 가지고와 5 와 6을 Merge 합니다. { 4, 5, 6 } 이 한 집합이 되므로 4, 5, 6 사이에는 서로 경로가 존재합니다.

3)

 그 다음으로는 1 - 3 을 가지고와 1과 3을 Merge 합니다. { 1, 3 } / { 4, 5, 6 }

4)

 그 다음으로는 0 - 2 를 가지고와 0과 2를 Merge 합니다. { 0, 2 }  / { 1, 3 } / { 4, 5, 6 }

5)

 그 다음으로는 2 - 6을 가지고와 2와 6을 Merge 합니다. { 0, 2, 4, 5, 6 } / { 1, 3 }

6)

 그 다음으로는 1 - 2를 가지고와 1과 2를 Merge 합니다. { 0, 1, 2, 3, 4, 5, 6 }

이때, 3과 5가 같은 집합으로 합쳐졌으므로 3 - 5 사이에 경로가 존재하게 되므로 함수를 종료하면 됩니다.

#include<iostream>
#include<queue>

using namespace std;

int p, w, root[1000], startNode, endNode, x, y, z;

int find(int num) {
	if (root[num] == num)
		return num;
	return root[num] = find(root[num]);
}

void merge(int num1, int num2) {
	int pNum1 = find(num1);
	int pNum2 = find(num2);
	if (pNum1 != pNum2) {
		root[pNum1] = pNum2;
	}
	return;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> p >> w >> startNode >> endNode;
	for (int i = 0; i < p; i++)
		root[i] = i;

	priority_queue<pair<int, pair<int, int>>> q;
	for (int i = 0; i < w; i++) {
		cin >> x >> y >> z;
		q.push({ z, {x, y} });
	}
	while (!q.empty()) {
		pair<int, pair<int, int>> cur = q.top();
		q.pop();

		merge(cur.second.first, cur.second.second);

		if (find(startNode) == find(endNode)) {
			cout << cur.first << '\n';
			break;
		}
	}
	return 0;
}

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

[ 알고리즘풀이 ]

 BFS 탐색과 Union-Find 로 문제를 해결할 수 있습니다.

1) 먼저, 입력 받은 문명지들마다 Numbering 을 해줍니다.

2) 입력 받은 문명지들을 순회하며 주변에 다른 문명이 있다면 Union-Find 를 통해 문명을 결합합니다. 처음에는 K개의 문명이 있지만, 문명을 결합할 때마다 문명의 개수를 K-- 를 통해 낮춰줍니다.

3) 문명의 개수가 1인지 체크하고, 1이라면 종료합니다.

4) 1이 아니라면, 문명지들을 다시 주변으로 전파해줍니다. 그 후, 2번부터 다시 반복합니다.

// 문제의 핵심은 문명을 먼저 결합하고, 그 뒤에 전파해야됩니다! 

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

int N, K, x, y, root[4000000];
int map[2000][2000];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };

queue<pair<int, int>> q1, q2;

int find(int num) {
	if (root[num] == num)
		return num;
	return root[num] = find(root[num]);
}

bool merge(int num1, int num2) {
	int pNum1 = find(num1), pNum2 = find(num2);
	if (pNum1 == pNum2)
		return false;
	root[pNum1] = pNum2;
	return true;
}

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

	cin >> N >> K;

	for (int i = 0; i < N * N; i++)
		root[i] = i;

	for (int i = 1; i <= K; i++) {
		cin >> x >> y;
		x--, y--;
		map[x][y] = i;
		q1.push({ x, y });
	}

	int ans = 0, curCivil = K;
	while (1) {
		// 문명 결합
		int qSize = q1.size();
		for (int i = 0; i < qSize; i++) {
			pair<int, int> cur = q1.front();
			q1.pop();
			q2.push(cur);
			int x = cur.first, y = cur.second;

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j], ny = y + dy[j];
				if (!(0 <= nx && nx < N && 0 <= ny && ny < N))
					continue;
				if (map[nx][ny] != 0) {
					bool check = merge(map[x][y], map[nx][ny]);
					if (check)
						curCivil--;
				}
			}
		}
		if (curCivil == 1)
			break;
		// 문명전파
		qSize = q2.size();
		for (int i = 0; i < qSize; i++) {
			pair<int, int> cur = q2.front();
			q2.pop();

			int x = cur.first, y = cur.second;
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j], ny = y + dy[j];
				if (!(0 <= nx && nx < N && 0 <= ny && ny < N))
					continue;
				if (map[nx][ny] == 0) {
					q1.push({ nx, ny });
					map[nx][ny] = map[x][y];
				}
			}
		}
		ans++;
	}
	cout << ans << '\n';
	return 0;
}