백준 알고리즘 기초 - 그래프1 (연결요소, 이분그래프, 그래프 예제)

요즘 오후 시간이 유독 힘들다..

체력적인 문제라기보다는 멘탈의 문제인듯 하다.

좀 더 단계적인 목표를 세우고 효율적으로 움직여보자.

정리 시작!

-

* 연결 요소 : 연결 되지 않고 나눠진 각각의 그래프. 연결 요소의 개수는 dfs, bfs로 구할 수 있다.

11724번: 연결 요소의 개수

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

int n, m;
vector<int>s[1001];
bool check[1001];

void dfs(int x) {
	check[x] = true;
	for (int i = 0; i < s[x].size(); i++) {
		int y = s[x][i];
		if (check[y] == false) {
			dfs(y);
		}
	}
}

int main()
{
	cin >> n >> m;
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		s[a].push_back(b);
		s[b].push_back(a);
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (check[i] == false) {
			dfs(i);
			ans += 1;
		}
	}

	cout << ans << '\n';

	return 0;
}

 - 모든 정점이 연결되어 있으면 dfs가 한번만 호출될 것이고, 연결 요소 상태라면 그 개수만큼 호출될 것이다.

 

* 이분 그래프 : A에 포함된 정점끼리 연결된 간선이 없고, B에 포함된 정점끼리 연결된 간선이 없는 A<->B 형식의 그래프다. 중요한 개념이니 확실히 알고 넘어가자. 어떻게 풀지 잘 안 떠올라서 한참 고민했다.

1707번: 이분 그래프

#include <iostream>
#include <vector>

using namespace std;

vector<int> a[20001];
int color[20001];
int v, e;

bool dfs(int x, int c) {
	color[x] = c;
	for (int i=0; i<a[x].size(); i++) {
		int y = a[x][i];
		if (color[y] == 0) {
			if (dfs(y, 3 - c) == false) {
				return false;
			}
		}
		else if (color[x] == color[y]) {
			return false;
		}
	}
	return true;
}

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

	while (t--) {
		cin >> v >> e;

		for (int i = 1; i <= v; i++) {
			a[i].clear();
			color[i] = 0;
		}

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

		bool okay = true;
		for (int i = 1; i <= v; i++) {
			if (color[i] == 0) {
				if (dfs(i, 1) == false) {
					okay = false;
				}
			}
		}

		if (okay) cout << "YES" << '\n';
		else cout << "NO" << '\n';
	}

	return 0;
}

 - 1과 2로 이분하는 것이므로, 한쪽 정점에 i가 들어갔으면 연결된 정점은 3-i라고 할 수 있다. 이걸 생각하는 게 관건이었다. 연결된 정점이 같은 색인 예외를 모두 패스하면 조건이 성립한다고 할 수 있다.

- 다음부터는 그래프 예제다. dfs나 bfs로 해결 가능한데, bfs로 푸는 게 더 편해서 거의 bfs로 풀었다.

 

* 단지번호붙이기 (low) : 단지의 수와 각 단지내 집의 수를 오름차순으로 출력하는 문제다.

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

2667번: 단지번호붙이기

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

int n;
int map[25][25];
bool check[25][25];

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

int bfs(int x, int y)
{
	int ans = 0;
	queue< pair<int, int> > q;
	check[x][y] = true;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		pair<int, int> r = q.front();
		ans += 1;
		int t1 = r.first;
		int t2 = r.second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int a = t1 + mx[i];
			int b = t2 + my[i];
			if (a >= 0 && a < n && b>=0 && b < n) {
				if (map[a][b] == 1 && check[a][b] == false) {
					check[a][b] = true;
					q.push(make_pair(a, b));
				}
			}
		}
	}
	return ans;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &map[i][j]);
		}
	}

	int cnt = 0;
	vector<int> ans;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && check[i][j] == false) {
				ans.push_back(bfs(i, j));
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	sort(ans.begin(), ans.end());
	for (int i = 0; i < cnt; i++)
		cout << ans[i] << '\n';

	return 0;
}

 - 집 수를 어디서 어떤 식으로 셀 것인지만 잘생각해주면 어려운 점은 없었다.

 

* 섬의 개수 (low) : 이번엔 대각선에 있는 것도 포함해서 세준다.

4963번: 섬의 개수

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

int w, h;
int map[50][50];
bool check[50][50];

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

void bfs(int x, int y)
{
	queue< pair<int, int> > q;
	check[x][y] = true;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		pair<int, int> r = q.front();
		int t1 = r.first;
		int t2 = r.second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			int a = t1 + mx[i];
			int b = t2 + my[i];
			if (a >= 0 && a < h && b >= 0 && b < w) {
				if (map[a][b] == 1 && check[a][b] == false) {
					check[a][b] = true;
					q.push(make_pair(a, b));
				}
			}
		}
	}
}

int main()
{

	cin >> w >> h;
	while (w != 0 && h != 0) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[i][j];
				check[i][j] = false;
			}
		}
		int ans = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == 1 && check[i][j] == false) {
					bfs(i, j);
					ans += 1;
				}
			}
		}
		cout << ans << '\n';
		cin >> w >> h;
	}

	return 0;
}

 - 위의 문제에서 상,하,좌,우 로 가던 걸, 대각선도 포함해서 생각해주기만 하면 된다.

 

* 미로 탐색 (mid) : 너무 어렵게 생각해서 좀 헤맸다. 단순한 bfs 문제다.

2178번: 미로 탐색

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

int n, m;
int maze[101][101];
int dist[101][101];
bool check[101][101];

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

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &maze[i][j]);
		}
	}
	
	queue<pair<int, int> > q;
	check[1][1] = true; 
	dist[1][1] = 1;
	q.push(make_pair(1, 1));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int px = x + mx[i];
			int py = y + my[i];
			if (px >= 1 && px <= n && py >= 1 && py <= m) {
				if (maze[px][py] == 1 && check[px][py] == false) {
					dist[px][py] = dist[x][y] + 1;
					check[px][py] = true;
					q.push(make_pair(px, py));
				}
			}
		}
	}

	cout << dist[n][m] << '\n';

	return 0;
}

 - 누적 이동 값을 구하는 배열을 하나 더 선언해서 기록해나가는 것을 생각했느냐가 관건이었다. 그냥 bfs 사용해서 +1씩 해주면 답 나온다. 어렵게 생각할 거 없다....

 

* 토마토 (mid) : 많이 헤맸다. 왜 그랬을까.. 위의 문제랑 거의 똑같은 문제다..

7576번: 토마토

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

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

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

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

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ix = x + mx[i];
			int iy = y + my[i];
			if (ix >= 0 && ix < n && iy >= 0 && iy < m) {
				if (a[ix][iy] == 0 && d[ix][iy] == -1) {
					d[ix][iy] = d[x][y] + 1;
					q.push(make_pair(ix, iy));
				}
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (ans < d[i][j]) {
				ans = d[i][j];
			}
		}
	}

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

	cout << ans << '\n';

	return 0;
}

 - 위의 문제와 다른 점은, 토마토가 있는 곳의 거리는 다 0으로 초기화 해주고 큐에 미리 넣어놔 거기서부터 확인해나가면 된다는 점이다. 이걸 생각 못 해서 많이 헤맸던 것 같다.

 

* 나이트의 이동 (mid) : 경우가 좀 특이하다는 것만 빼면 위의 문제들과 별로 다를 게 없다.

7562번: 나이트의 이동

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

int d[300][300];
int mx[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int my[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
int n;

int bfs(int x1, int y1, int x2, int y2) {
	queue<pair<int, int> > q;
	d[x1][y1] = 0;
	q.push(make_pair(x1, y1));

	if (x1 == x2 && y1 == y2) {
		return d[x1][y1];
	}

	while (!q.empty()) {
		int t1 = q.front().first;
		int t2 = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			int x = t1 + mx[i];
			int y = t2 + my[i];
			if (x >= 0 && x < n && y >= 0 && y < n) {
				if (d[x][y] == -1) {
					d[x][y] = d[t1][t2] + 1;
					q.push(make_pair(x, y));
				}
			}
		}
	}
	return d[x2][y2];
}

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

	while (t--) {
		cin >> n;

		int x1, y1, x2, y2;
		cin >> x1 >> y1;
		cin >> x2 >> y2;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = -1;
			}
		}

		int ans = bfs(x1, y1, x2, y2);

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

	return 0;
}

 - 출발 지점을 0으로 초기화하고, +1 씩 bfs 해나가면 된다. 모든 경우가 끝나고 난 뒤에 도착지의 이동 횟수를 취하면 되겠다.

-

처음엔 강의가 몇 분 안 되서 금방 듣겠다 했는데.. 문제를 풀어보고 강의를 들어야 하니..

15분 짜리 강의를 듣는데 몇 시간이 걸리는 지 모르겠다.. 문제가 안 풀리면 짜증도 나고 하니

멘탈도 흔들리고.. 그러는 것 같다. 좀 더 여유를 가지고, 안 풀리면 바람도 좀 쐬다가, 그래도 안 되면

정답 따라하면서 연습하고 그렇게 하면 된다. 너무 조급해 하지 말자! 그래프 챕터도 마무리 잘 하길..

정리 끝!