백준 알고리즘 기초 - 그래프1 (도전)

도저어언

푹 쉬고 나니 좀 낫다.

뭘 해도 건강이 우선이다.

다시 차근차근 해나가보자.

정리 시작.

-

* BFS 스페셜 저지 (mid) : 주어진 경우가 bfs 탐색이 맞는지 확인하는 문제다.

16940번: BFS 스페셜 저지

- 처음엔 단순하게 모든 bfs 경우를 생각했을 때 해당 경우가 나오는지 생각해서 풀어봤다.

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

int n, cnt = 1;
vector<int> a[100000], ans;
bool check[100000];

void bfs(int e) {
	queue<int> q;
	check[e] = true;
	q.push(e);

	while (!q.empty()) {
		int x = q.front();
		q.pop();

		vector<int> tmp;
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (check[y] == false) {
				tmp.push_back(y);
			}
		}

		for (int i = 0; i < tmp.size(); i++) {
			for (int j = 0; j < tmp.size(); j++) {
				int y = tmp[j];
				if (ans[cnt] == y) {
					check[y] = true;
					q.push(y);
					cnt += 1;
				}
			}
		}
	}
}

int main()
{
	cin >> n;

	int x, y;
	for (int i = 0; i < n - 1; i++) {
		cin >> x >> y;
		x -= 1; y -= 1;
		a[x].push_back(y);
		a[y].push_back(x);
	}

	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		t -= 1;
		ans.push_back(t);
	}

	bfs(0);

	if (cnt == n) cout << 1 << '\n';
	else cout << 0 << '\n';

	return 0;
}

 - 방문하지 않은 연결된 정점을 따로 저장해두고, 입력한 순서대로 확인 해나간다. 

 - 입력한 값이 있으면 큐에 push하고 cnt를 늘려가면서 비교해주고, 마지막에 cnt 값이 n과 같으면 bfs 탐색을 올바르게 한 것이다.

 - 이것도 나쁘지 않은 방법인데, 무조건 다 확인을 해야 알 수 있다는 단점이 있다. 예외 처리가 잘 되어 있는 정답 코드도 참고 해봤다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> a[100000];
int parent[100000];
int order[100000];
bool check[100000];

int main() {
	int n;
	cin >> n;

	for (int i = 0; i<n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u -= 1; v -= 1;
		a[u].push_back(v);
		a[v].push_back(u);
	}

	for (int i = 0; i<n; i++) {
		cin >> order[i];
		order[i] -= 1;
	}

	queue<int> q;
	q.push(0);
	check[0] = true;

	int m = 1; // 큐의 크기
	for (int i = 0; i<n; i++) {
		if (q.empty()) { // 아직 BFS가 진행 중인데 큐가 비어있을 때
			cout << 0 << '\n';
			return 0;
		}
		int x = q.front(); q.pop();
		if (x != order[i]) { // 순서가 올바르지 않을 때
			cout << 0 << '\n';
			return 0;
		}
		int cnt = 0; // 이번에 큐에 넣어야 할 정점의 수
		for (int y : a[x]) {
			if (check[y] == false) {
				parent[y] = x;
				cnt += 1;
			}
		}
		for (int j = 0; j<cnt; j++) { // 아까 큐에 넣은 수만 나와야 함
			if (m + j >= n || parent[order[m + j]] != x) { // X와 연결되지 않은 정점이 큐에 들어가있으니 올바르지 않음
				cout << 0 << '\n';
				return 0;
			}
			q.push(order[m + j]);
			check[order[m + j]] = true;
		}
		m += cnt;
	}
	cout << 1 << '\n';
	return 0;
}

 - 수시로 bfs 여부를 확인하는 장치가 들어가 있다. bfs가 끝나기도 전에 큐가 비어있을 때, 큐에 삽입된 값이 주어진 경우와 순서가 다를 때, 연결되지 않은 정점이 큐에 들어가 있을 때 조건을 성립하지 않는다.

 - 가장 핵심적인 요령은 연결된 정점을 parent 배열에 저장하는 것이다. 해당 정점의 부모가 무엇인지 기록함으로써, 주어진 순서대로 비교를 할 때, parent 배열이 정점의 연결 순서를 고려하지 않아도 되게 한다.

 

* DFS 스페셜 저지 (mid) : 같은 원리로 dfs도 풀어볼 수 있다.

16964번: DFS 스페셜 저지

#include <iostream>
#include <vector>

using namespace std;

int n, cnt = 0;
vector<int> a[100000], ans;
bool check[100000];

void dfs(int x) {
	check[x] = true;
	cnt += 1;

	vector <int> temp;
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		if (check[y] == false) {
			temp.push_back(y);
		}
	}

	if (temp.size() > 0) {
		for (int i = 0; i < temp.size(); i++) {
			for (int j = 0; j < temp.size(); j++) {
				int y = temp[j];
				if (cnt < n) {
					if (ans[cnt] == y) {
						dfs(y);
					}
				}
			}
		}
	}
}

int main()
{
	cin >> n;

	int x, y;
	for (int i = 0; i < n - 1; i++) {
		cin >> x >> y;
		x -= 1; y -= 1;
		a[x].push_back(y);
		a[y].push_back(x);
	}

	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		t -= 1;
		ans.push_back(t);
	}

	dfs(0);

	if (cnt == n) cout << 1 << '\n';
	else cout << 0 << '\n';

	return 0;
}

 - 위의 bfs 문제를 푼 첫번째 방법으로 dfs를 풀었다. 이것도 끝까지 다 확인 해봐야 아는 방법이다. 이 또한 정답 코드가 있지만, 속도 차이가 크지 않고 괜히 복잡하기만 한 것 같아 굳이 올리지는 않겠다.

 

* 다리 만들기 (high) : 섬과 섬 사이에 놓을 수 있는 최소 길이의 다리 길이를 구하는 문제다.

2146번: 다리 만들기

 - 일단 섬을 구분해서 표시하고, 각 섬에서 다른 섬까지의 길이 중 최솟값을 구하면 된다고 생각할 수 있다.

#include <iostream>
#include <queue>

using namespace std;

int a[100][100], d[100][100], g[100][100];

int mx[] = { 0,0,1,-1 };
int my[] = { 1,-1,0,0 };

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (a[i][j] == 1 && g[i][j] == 0) {
				queue <pair <int, int> > q;
				g[i][j] = ++cnt;
				q.push(make_pair(i, j));

				while (!q.empty()) {
					int tx = q.front().first;
					int ty = q.front().second;
					q.pop();
					
					for (int k = 0; k < 4; k++) {
						int ax = tx + mx[k];
						int ay = ty + my[k];
						if (ax >= 0 && ax < n && ay >= 0 && ay < n) {
							if (a[ax][ay] == 1 && g[ax][ay] == 0) {
								g[ax][ay] = cnt;
								q.push(make_pair(ax, ay));
							}
						}
					}
				}
			}
		}
	}

	int ans = -1;
	for (int k = 1; k <= cnt; k++) {
		queue <pair<int, int> > q;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = -1;
				if (g[i][j] == k) {
					q.push(make_pair(i, j));
					d[i][j] = 0;
				}
			}
		}

		while (!q.empty()) {
			int tx = q.front().first;
			int ty = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int ax = tx + mx[i];
				int ay = ty + my[i];
				if (ax >= 0 && ax < n && ay >= 0 && ay < n) {
					if (d[ax][ay] == -1) {
						d[ax][ay] = d[tx][ty] + 1;
						q.push(make_pair(ax, ay));
					}
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][j] == 1 && g[i][j] != k) {
					if (ans == -1 || d[i][j] - 1 < ans) {
						ans = d[i][j] - 1;
					}
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

 - 먼저 bfs를 통해 섬을 구분짓는다. 그 다음 섬 별로 다른 섬까지의 거리의 최솟값을 구해서 그 중 최솟값이 답이 되는 형태다.

 - 각 섬 별로 따로 값을 구해야 하기 때문에 시간 소요가 많다. 따로 구하지 말고, 같이 구할 수 있는 방법은 없을까..?

 - 섬에서의 거리를 늘려나갈 때 섬의 범위도 늘려간다고 생각하면, 각각 다른 섬의 범위가 맞닿는 경우가 생길 거다. 그럼 각각의 섬 범위까지의 거리를 더하면 두 섬을 잇는 다리의 길이가 될 것이다. 이 중 최솟값을 구하면 된다.

#include <iostream>
#include <queue>

using namespace std;

int a[100][100], d[100][100], g[100][100];

int mx[] = { 0,0,1,-1 };
int my[] = { 1,-1,0,0 };

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (a[i][j] == 1 && g[i][j] == 0) {
				queue <pair <int, int> > q;
				g[i][j] = ++cnt;
				q.push(make_pair(i, j));

				while (!q.empty()) {
					int tx = q.front().first;
					int ty = q.front().second;
					q.pop();
					
					for (int k = 0; k < 4; k++) {
						int ax = tx + mx[k];
						int ay = ty + my[k];
						if (ax >= 0 && ax < n && ay >= 0 && ay < n) {
							if (a[ax][ay] == 1 && g[ax][ay] == 0) {
								g[ax][ay] = cnt;
								q.push(make_pair(ax, ay));
							}
						}
					}
				}
			}
		}
	}

	queue <pair<int, int> > q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = -1;
			if (a[i][j] == 1) {
				q.push(make_pair(i, j));
				d[i][j] = 0;
			}
		}
	}
	while (!q.empty()) {
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ax = tx + mx[i];
			int ay = ty + my[i];
			if (ax >= 0 && ax < n && ay >= 0 && ay < n) {
				if (d[ax][ay] == -1) {
					d[ax][ay] = d[tx][ty] + 1;
					g[ax][ay] = g[tx][ty];
					q.push(make_pair(ax, ay));
				}
			}
		}
	}

	int ans = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 4; k++) {
				int x = i + mx[k];
				int y = j + my[k];
				if (x >= 0 && x < n && y >= 0 && y < n) {
					if (g[i][j] != g[x][y]) {
						if (ans == -1 || d[i][j] + d[x][y] < ans) {
							ans = d[i][j] + d[x][y];
						}
					}
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

 - 여러번 계산을 할 필요가 없기 때문에 속도가 대폭 줄어든다. 

 - 이전에 풀었던 단지 번호 붙이기와 토마토 문제를 합쳐 놓은 문제라고 보면 된다.

-

다음 챕터에서 bfs를 한번 더 다룬다. 그만큼 중요한 알고리즘이다.

최대한 많은 문제를 풀어보고 익숙해지자.

정리 끝!