[BOJ] 2468 안전 영역 - BFS / Union-Find

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

 

문제 풀이 1 - BFS:

입력 중 가장 높은 지역의 높이를 maxH라고 하자.

모든 높이에 대해 다음 연산을 수행한다.

현재 높이를 h라고 할 때, h보다 큰 값들을 bfs를 통해 덩어리의 개수를 구한다.

이때 visit 변수를 사용하게 되는데 높이마다 새롭게 visit 변수를 표시해야 한다. 

이를 memset을 이용하여 초기화해도 되지만, 이렇게 하면 시간을 더 소비하게 된다.

그래서 나는 visit을 true, false로 표시하는 것 대신, 현재 높이로 방문한 사실을 기록하여 visit 변수 초기화하지 않아도 되도록 하였다.

 

시간: 668ms

 

소스 코드:

 

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

int n,arr[102][102],res,maxH,visit[102][102];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool exist[102];
typedef pair<int, int> P;

P startPoint(int h) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] > h && visit[i][j]<h) {
				return make_pair(i, j);
			}
		}
	}
	return make_pair(-1, -1);
}
void counter(P start, int h) {
	queue<P> q;
	q.push(start);
	visit[start.first][start.second] = h;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx < 0 || xx >= n || yy < 0 ||
				yy >= n || visit[xx][yy]==h||arr[xx][yy]<=h) continue;
			visit[xx][yy] = h;
			q.push({ xx,yy });
		}
	}
}
void func() {
	res = 1;
	for (int i = 1; i <= 100; i++) {
		if (!exist[i]) continue;
		int cnt = 0;
		while (1) {
			P start = startPoint(i);
			if (start.first == -1) break;
			cnt++;
			counter(start, i);
		}
		res = max(res, cnt);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			exist[arr[i][j]] = true;
		}
	}
	func();
	cout << res << '\n';

	return 0;
}

 

 

문제 풀이 2 - UNION FIND:

유니온 파인드 알고리즘을 사용하여 시간 복잡도를 줄일 수 있다.

이번에는 maxH부터 높이를 줄여가며 연산을 한다.

 

변수 설명:

arr[x][y]: (x,y) 지역의 높이를 가짐

p[i]: i(x*n+y) 지역의 group number를 가짐

cnt: 현재 높이에서 덩어리의 개수

 

1. p 배열을 -1로 초기화해준다.

2. 현재 높이보다 큰 값을 가지는 지역을 찾는다.

3. 이 지역의 group number가 -1이라면(어떤 group에도 속하지 않음), 새로운 지역이 수면 위로 드러난 것이기 때문에 cnt++;, group number = 자기 자신의 위치

4. 인접한 곳 중 수면 위로 드러나 있는 지역(group number을 가진 지역이어야 함)이 있다면 merge -> 두 덩어리가 합쳐졌다는 말이므로 cnt--;

5. 현재 높이를 줄인다 (h--;)

6. h가 0이 될 때까지 1~5 단계 반복

 

 

소스 코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <string>
using namespace std;

int n,arr[101][101],res,maxH,p[101*101],cnt;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
typedef pair<int, int> P;

int find(int x) {
	if (p[x]<0||p[x]==x) return x;
	return p[x] = find(p[x]);
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		p[a] = b;
		cnt--;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			maxH = max(maxH, arr[i][j]);
		}
	}
	memset(p, -1, sizeof(p));
	res = 1;
	for (int h = maxH - 1; h >0; h--) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[i][j] >h) {
					int pos = i * n + j;
					if (p[pos] == -1) {
						p[pos] = pos;
						cnt++;
					}
					for (int k = 0; k < 4; k++) {
						int xx = i + dx[k];
						int yy = j + dy[k];
						if (xx < 0 || xx >= n || yy < 0 ||
							yy >= n || arr[xx][yy] <= h ||p[xx*n+yy]==-1) continue;
						merge(pos, xx * n + yy);
					}
				}
			}
		}
	
		res = max(res, cnt);
	}
	cout << res<<'\n';
	
	return 0;
}