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

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

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

int n, k, area = 0;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int arr[2001][2001];
int unf[100001];

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));

    int t = 0;
    int comp;

    queue<pair<int, int> > Q;
    queue<int> region;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        arr[a][b] = ++area;
        region.push(area);
        comp = arr[a][b];
        Q.push({ a,b });
    }


    int q = Q.size();
    for (int i = 0; i < q; i++) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();

        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
            if (arr[nx][ny] > 0) {
                merge(arr[x][y], arr[nx][ny]);
            }
        }
        Q.push({ x,y });
    }



    while (!region.empty() && Find(comp) == Find(region.front())) {
        region.pop();
    }
    if (region.empty()) {
        cout << t << '\n';
        return 0;
    }
  
    while (!Q.empty()) {
        int q = Q.size();
        for (int i = 0; i < q; i++) {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;

                if (arr[nx][ny] == 0) {
                    arr[nx][ny] = arr[x][y];
                    Q.push({ nx, ny });
                }
                else if (Find(arr[x][y]) != Find(arr[nx][ny])) {
                    merge(arr[x][y], arr[nx][ny]);
                }
            }
        }
        t++;

        //인접한 곳에 union 되지 않은 영역 있는지 체크 
        q = Q.size();
        for (int i = 0; i < q; i++) {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
                if (arr[nx][ny] > 0) {
                    merge(arr[x][y], arr[nx][ny]);
                }
            }
            Q.push({ x,y });
        }

		while (!region.empty() && Find(comp) == Find(region.front())) {
            region.pop();
        }
        if (region.empty()) {
            cout << t << '\n';
            return 0;
        }

    }
    
    return 0;
}

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

1. 문제설명

주어진 그래프를 오일러 회로 or 오일러 경로로 만드려면

몇개의 간선이 추가로 필요한지 구해야 하는 문제입니다.

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

주어진 그래프에서

Union & Find 알고리즘을 이용해

서로 다른 컴포넌트면서 차수가 0이거나 홀수인 노드를 우선 연결해주고

그 이후에도 서로 다른 컴포넌트가 남아있다면

컴포넌트 개수가 1이 될 때까지 모두 연결해준뒤

한붓그리기가 가능한

오일러 회로나 오일러 경로가 되려면

차수가 홀수인 노드가 최대 2개여야 하므로

차수가 홀수인 노드의 개수를 센 다음에

간선을 몇개 더 이어줘야하는지 구하면 답을 구할 수 있습니다.

3.문제풀이코드 C++

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

int v, e, area, ans;
int degree[1001];
int unf[1001];

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

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) unf[a] = b;
}


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

    cin >> v >> e;

    for (int i = 1; i <= v; i++) {
        unf[i] = i;
    }


    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;

        degree[a]++;
        degree[b]++;
        Union(a, b);
    }

    //1. 서로 다른 컴포넌트이며 둘 다 차수가 홀 수거나 0이면 이어준다.
    for (int i = 1; i <= v; i++) {
        for (int j = i + 1; j <= v; j++) {
            if ((degree[i] % 2 == 1 || degree[i]==0) && 
                (degree[j] % 2 == 1||degree[j]==0) && 
                (Find(i) != Find(j))) {
                Union(i, j);
                degree[i]++;
                degree[j]++;
                ans++;
            }
        }
    }

    //2. 둘다 차수가 짝수여도 서로 다른 컴포넌트일 경우 서로 이어준다.
    for (int i = 1; i <= v; i++) {
        for (int j = i + 1; j <= v; j++) {
            if (Find(i) != Find(j)) {
                Union(i, j);
                degree[i]++;
                degree[j]++;
                ans++;
            }
        }
    }

    int odd = 0;
    for (int i = 1; i <= v; i++) {
        if (degree[i] % 2 == 1) {
            odd++;
        }
    }


    //3. 차수가 홀 수 인 게 2개이상인 경우 그만큼 연결해주어야한다.
    ans += (odd - 2 > 0) ? ((odd - 2) / 2) : 0;

    cout << ans << '\n';
   
    return 0;
}

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

1. 컴포넌트 수가 1개여야 한다.

2. 오일러 회로이거나 오일러 경로여야한다. (차수가 홀수인 노드가 2개거나 0개여야한다)

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

struct Edge {
    int to, c;
    Edge* dual;
    Edge() : Edge(-1, 0) {};
    Edge(int to1, int c1) :to(to1), c(c1), dual(nullptr) {};
};


vector<Edge*> adj[3001];
int v,e,degree[3001];
int odd;
bool visited[3001];

int DFS(int x) {
    int res = 1;
    visited[x] = 1;
    for (Edge* e : adj[x]) {
        if (e->c > 0 && visited[e->to]==0) {
            e->c--;
            e->dual->c--;
            res += DFS(e->to);
        }
    }
    return res;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int a,b;
        cin >> a >> b;
        Edge* e1 = new Edge(b, 1), *e2 = new Edge(a,1);
        e1->dual = e2;
        e2->dual = e1;

        adj[a].push_back(e1);
        adj[b].push_back(e2);

        degree[a]++;
        degree[b]++;
    }

    for (int i = 1; i <= v; i++) {
        if (degree[i] % 2 == 1) {
            odd++;
        }

        if (odd > 2) {
            cout << "NO";
            return 0;
        }
    }

    bool flag = false;

    for (int i = 1; i <= v; i++) {
        if (!visited[i]) {
            int res = DFS(i);
            if (res > 1) {
                if (flag) {
                    cout << "NO";
                    return 0;
                }
                else {
                    flag = true;
                }
            }
        }
    }

    cout << "YES";

    return 0;
}