https://www.acmicpc.net/problem/10971

1. 문제설명

외판원 순회 문제입니다.

시작점을 정해주지 않았기 때문에 모든 노드에서 시작할 수 있습니다.

우선순위큐를 이용해서 최단거리를 우선으로 방문해야 메모리와 시간을 아낄 수 있습니다.

시험삼아 우선순위큐만 큐로 바꿔서 돌려봤습니다.

메모리 63072KB, 360ms 걸린 게 일반 큐를 이용한 것이고

메모리 2500KB, 4ms가 우선순위 큐를 이용한 것입니다.

메모리와 시간차이가 나는 이유는

우선순위큐를 이용할 때는 최단거리를 우선으로 방문하고 그 이외에는 방문하지 않는데

큐를 이용할 때는 이미 방문했던 점이 최단거리가 아닐 수 있기 때문에

계속해서 해당 노드의 해당 상태에 대해 불필요한 계산이 이루어져서

시간과 메모리가 많이 사용됩니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>

int ch[11][1 << 11];
int n, arr[11][11];

struct Node {
	int cur, vis, st, dist;
	bool operator<(const Node& b) const {
		return dist > b.dist;
	}
};

using namespace std;
int main() {


	priority_queue<Node> Q;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
		Q.push({ i,1 << i,i ,0 });
	}

	int ans = INT_MAX;

	while (!Q.empty()) {
		int cur = Q.top().cur;
		int vis = Q.top().vis;
		int st = Q.top().st;
		int dist = Q.top().dist;
		Q.pop();

		ch[cur][vis] = 1;

		if (vis == (1 << n) - 1) {
			if (arr[cur][st] != 0) ans = min(ans, dist + arr[cur][st]);
		}

		for (int i = 0; i < n; i++) {
			if (arr[cur][i] > 0 && ch[cur][vis | (1 << i)] == 0) {
				Q.push({ i,vis | (1 << i),st,dist + arr[cur][i] });
			}
		}
	}
	cout << ans << '\n';


	return 0;
}

https://www.acmicpc.net/problem/3780

1.문제설명

Union & Find, dis-joint set을 이용하는 문제입니다.

재귀를 잘 이용해서 거리를 잘 구해야 풀 수 있습니다.

부가적으로 제가 50%에서 계속 틀렸는데

거리를 구할 때 (i-j)%1000 이고

답을 구할 때 %1000을 해주면 안됩니다.

답은  (i-j)%1000을 모두 합한 값입니다

즉 1000을 넘어갈 수 도 있기 때문에 답에도 %1000을 해버리면 틀립니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;


int d[20003];
int unf[20003];


int Find(int x) {
	if (unf[x] < 0) return x;
	int idx = Find(unf[x]);

	d[x] += d[unf[x]];
	return unf[x] = idx;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	for (int T = 0; T < t; T++) {
		memset(unf, -1, sizeof(unf));
		memset(d, 0, sizeof(d));
		int n;
		cin >> n;

		char c;

		while (1) {
			cin >> c;

			if (c == 'E') {
				int k;
				cin >> k;
				Find(k);
				cout << d[k] << '\n';
			}
			else if (c == 'I') {
				int a, b;
				cin >> a >> b;
				unf[a] = b;
				d[a] = (abs(a - b) % 1000);
			}
			else if (c == 'O') {
				break;
			}
		}
	}

	return 0;
}

https://www.acmicpc.net/problem/17398

1. 문제설명

노드를 이어주는 간선을 제거했을 때

컴포넌트의 수가 증가한다면 각 컴포넌트의 노드 개수를 곱해서 결괏값에 더해야합니다.

이 문제는 이 방법대로 해결하기보다 역으로 생각해야 쉽게 풀 수 있습니다.

2.접근방법[알고리즘]

Union & Find 알고리즘을 응용합니다.

분할의 반대는 병합입니다. 

간선을 제거할 때 나눠지는 컴포넌트 노드의 수를 곱하는 대신

병합하기전 컴포넌트의 노드의 수를 곱하고 병합하면 더 쉽게 해결할 수 있습니다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, q;
vector<pair<int, int> > v(1);
bool ch[100003];
vector<int> del;
int unf[100003];

int Find(int x) {
	if(unf[x] < 0) return x;

	return unf[x] = Find(unf[x]);
}

//루트에 하위 노드의 개수를 저장합니다
void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a == b) return;

	if (unf[a] <= unf[b]) {
		unf[a] += unf[b];
		unf[b] = a;
	}
	else {
		unf[b] += unf[a];
		unf[a] = b;
	}
}

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

	memset(unf, -1, sizeof(unf));

	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}

	for (int i = 0; i < q; i++) {
		int a;
		cin >> a;
		ch[a] = 1;
		del.push_back(a);
	}

	for (int i = 1; i <= m; i++) {
		if (ch[i] == 0) {
			Union(v[i].first, v[i].second);
		}
	}

	long long ans = 0;
	for (int i = del.size() - 1; i >= 0; i--) {
		int a = v[del[i]].first;
		int b = v[del[i]].second;

		if (Find(a) != Find(b)) {
			ans += (unf[Find(a)] * unf[Find(b)]);
		}
		Union(a, b);
	}

	cout << ans << '\n';


	return 0;
}

주의할점 : 정답이 INT_MAX를 넘어갑니다.

https://www.acmicpc.net/problem/15459

1. 문제설명

영어로 된 문제여서 구글 번역을 한번 돌리면 좀 더 쉽게 이해가 가능합니다.

Union & Find 알고리즘을 이용하여 문제를 해결했습니다.

N개의 Haybale을 spiceness에 대해 오름차순으로 정렬합니다.

spiceness가 작은 Haybale 부터 확인하면서 그 Haybale의 위 아래에 있는 Haybale 중

자신보다 spiceness가 작은 게 있으면 Union 해줍니다.

이 과정을 반복하다가

자신이 속한 집단의 flavor 값 합이 M 이상이 된다면

자신의 spiceness를 출력해주면 됩니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
int n;
long long m;
long long unf[100001];

pair<int, int> arr[100001];

struct Haybale {
	int node, flavor, spicy;
	bool operator<(const Haybale& b)const {
		return spicy < b.spicy;
	}
};

int Find(int x) {
	if (unf[x] < 0) return x;
	return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a == b) return;

	if (unf[a] >= unf[b]) {
		unf[b] += unf[a];
		unf[a] = b;
	}
	else {
		unf[a] += unf[b];
		unf[b] = a;
	}
}

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

	cin >> n >> m;
	vector<Haybale> v;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		arr[i] = { a,b };
		v.push_back({ i,a,b });
	}

	for (int i = 1; i <= n; i++) {
		unf[i] = -arr[i].first;
	}


	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		int node = v[i].node;

		if (node - 1 >= 1 && arr[node - 1].second <= arr[node].second) {
			Union(node - 1, node);
		}
		if (node + 1 <= n && arr[node].second >= arr[node + 1].second) {
			Union(node + 1, node);
		}

		if (-unf[Find(node)] >= m) {
			cout << arr[node].second;
			return 0;
		}
	}


	return 0;
}

m의 범위에 유의해야 메모리초과와 런타임에러를 방지할 수 있습니다.

https://www.acmicpc.net/problem/10775

1. 문제설명 및 접근방법[알고리즘]

g번 게이트가 이미 도킹 되었으면 g-1번 게이트가 비어있는지 확인하고

g-1번 게이트도 이미 도킹 되어있으면 g-2번 게이트를 확인해야 합니다.

이런 식으로 g-k 가 1번까지 갔을 때 1번마저 도킹이 되어있다면 더이상 도킹을 할 수 없습니다.

이걸 구현하기 위해서

dis-joint set(Union&Find) 알고리즘을 이용하여

현재 k번이 도킹되었다면 k와 k-1를 Union해주고 k-1이 루트가 되게 해줍니다.

그러면 다음에 Find(k)를 했을 때 아직 사용하지 않은 게이트인 k-1 번 게이트를 얻을 수 있습니다.

g번 게이트에 도킹할 때마다 Find(g)와 FInd(g)-1을 Union 해주면서

도킹을 할 수 없을 때까지 반복하는 코드를 구현합니다.

2.문제풀이 코드 C++

#include <bits/stdc++.h>
using namespace std;

int g,p,unf[100001], arr[100001];

int Find(int x) {
	if (unf[x] < 0) return x;
	return unf[x] = Find(unf[x]);
}


void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a == b) return;
	else if (a < b) {
		unf[b] = a;
	}
	else {
		unf[a] = b;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	memset(unf, -1, sizeof(unf));
	cin >> g >> p;

	int cnt = 0;
	for (int i = 0; i < p; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < p; i++) {
		int a = Find(arr[i]);
		
		if (a >= 1) {
			Union(a, a - 1);
			cnt++;
		}
		else {
			cout << cnt << '\n';
			return 0;
		}
	}

	cout << cnt << '\n';

	return 0;
}

https://www.acmicpc.net/problem/9938

Union&Find 알고리즘(dis-joint set)을 이용해서 풀어야 하는 문제다

풀이를 생각해내기 어려운 문제

#include <bits/stdc++.h>
using namespace std;


int n, l, unf[300001];
bool isfull[300001] ;

int Find(int x) {
	if (unf[x] < 0) return x;

	return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a == b) return;

	if (isfull[a]) {
		unf[a] = b;
	}
	else if (isfull[b]) {
		unf[b] = a;
	}
}

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

	memset(unf, -1, sizeof(unf));


	cin >> n >> l;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		if (!isfull[Find(a)]) {
			isfull[Find(a)] = 1;
			Union(a, b);
			cout << "LADICA\n";
		}
		else if (!isfull[Find(b)]) {
			isfull[Find(b)] = 1;
			Union(a, b);
			cout << "LADICA\n";
		}
		else {
			cout << "SMECE\n";
		}
	}

	return 0;
}

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

문제를 처음 봤을 때

DFS로 경로를 돌면서 최소 너비를 저장해 

최대의 최소 너비를 구해주고 싶은 생각이 들지만

그렇게 DFS를 돌 경우 모든 경우를 다 탐색하기 때문에 시간초과가 나게 됩니다.

Union & Find 알고리즘을 이용해서 해결해야합니다.

문제에서 주어지는 간선을 내림차 순으로 정렬하고

간선의 노드마다 Union 해주면서 최소한 어떤 너비의 간선까지 Union해주어야

시작지점과 도착지점이 연결되는지 구해야합니다.

#include <bits/stdc++.h>
using namespace std;

int p, w;
int unf[1001];

int Find(int x) {
	if (unf[x] < 0) return x;

	return unf[x] = Find(unf[x]);
}

void merge(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	unf[x] = y;
}

struct Edge {
	int a, b, c;
	bool operator<(const Edge& bb) const {
		return c > bb.c;
	}
};

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

	vector<Edge> v;
	memset(unf, -1, sizeof(unf));

	int st, end;
	cin >> p >> w;
	cin >> st >> end;
	for (int i = 0; i < w; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({ a,b,c });
	}
	int ans = INT_MAX;
	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		merge(v[i].a, v[i].b);
		ans = min(ans, v[i].c);

		if (Find(st) == Find(end)) {
			cout << ans << '\n';
			return 0;
		}
	}


	return 0;
}

https://www.acmicpc.net/problem/3197

#include <bits/stdc++.h>
using namespace std;

int r, c;
char arr[1501][1501];
int num[1501][1501];
int unf[1501 * 1501];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int Find(int x) {
	if (unf[x] < 0) return x;

	return unf[x] = Find(unf[x]);
}

void merge(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	unf[x] = y;
}

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

	memset(unf, -1, sizeof(unf));
	vector<pair<int, int> > swan;
	queue<pair<int, int> > water;

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		string s;
		cin >> s;

		for (int j = 0; j < c; j++) {
			arr[i][j] = s[j];
			if (arr[i][j] == 'L') {
				swan.push_back({ i,j });
				arr[i][j] = '.';
			}
			else if (arr[i][j] == 'X') {
				num[i][j] = -1;
				continue;
			}
			water.push({ i,j });
		}
	}

	//독립적으로 물이 있는 영역을 구해준다.
	int cnt = 1;
	queue<pair<int, int> > Q;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (num[i][j] == 0) {
				num[i][j] = cnt;
				Q.push({ i,j });
				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];
						if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
						if (num[nx][ny] == 0) {
							num[nx][ny] = num[x][y];
							Q.push({ nx,ny });
						}
					}
				}
				cnt++;
			}
		}
	}


	int t = 0;

	if (Find(num[swan[0].first][swan[0].second]) == Find(num[swan[1].first][swan[1].second])) {
		cout << t << '\n';
		return 0;
	}


	while (!water.empty()) {
		int q = water.size();

		//물로 빙하를 물로 만든다.
		for (int j = 0; j < q; j++) {
			int x = water.front().first;
			int y = water.front().second;
			water.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if (arr[nx][ny] == 'X') {
					arr[nx][ny] = '.';
					num[nx][ny] = num[x][y];
					water.push({ nx,ny });
				}
				else {
					merge(num[x][y], num[nx][ny]);
				}
			}
		}

		//현재 얼음이 물이 되어서 합쳐져야 될 영역이 있다면 합친다
		q = water.size();
		for (int j = 0; j < q; j++) {
			int x = water.front().first;
			int y = water.front().second;
			water.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if (arr[nx][ny] == '.') {
					merge(num[x][y], num[nx][ny]);
				}
			}
			water.push({ x,y });
		}

		t++;
		if (Find(num[swan[0].first][swan[0].second]) == Find(num[swan[1].first][swan[1].second])) {
			cout << t << '\n';
			return 0;
		}
	}




	return 0;
}