BOJ 16946) c++ 벽 부수고 이동하기 4 (분리 집합)

시간 제한 - 2s

메모리 제한 - 512MB

 

기존 1, 2, 3과는 다른 문제 유형

 

---

풀이

기존 벽 부수고 이동하기 1, 2, 3과는 다른 형식의 문제입니다.

정석대로라면 BFS, DFS를 통한 그래프 탐색문제로 풀 수 있지만, 그래프 탐색을 쓰지않은 풀이는 없는 것 같아서 이런 방법도 있다고 알려드리기 위해 포스팅합니다.

 

1. N * M 행렬을 순회하며 입력을 받으며 입력 값을 체크합니다.

2. 만약 입력 값이 0이라면 이미 지나왔으며 인접한 위, 왼쪽을 체크해 0인지 확인하고, 0이라면 두 좌표를 union 연산으로 묶어주고 두 그룹의 크기를 합쳐줍니다.

3. 입력이 끝난 시점에서 각 노드는 그룹이 완성된 상태입니다.

4. 다시 입력받은 배열을 순회하며 0이라면 그대로 출력, 1이라면 상하좌우 그룹의 크기를 더한 후 10을 나눈 나머지를 출력해줍니다.

 

입력

1 <= N, M <= 1000

(문제에서 최대 1,000,000개의 입력이 가능하지만, c++ 기준 입출력 최적화를 하지 않아도 통과했습니다.)

 

자료구조

char[N][M] NM개의 입력을 받기위한 배열입니다.

int[N][M] NM개의 노드의 부모노드를 나타내기 위한 배열입니다.(하기 코드에서는 1차원 배열로 변형해 사용)

추가로 각 그룹의 크기를 기록하기 위해 map, 상하좌우 그룹의 중복을 막기위해 set 사용

 

로직

1. N*M 크기의 배열을 순회하며 기존에 이미 연산이 끝난 왼쪽, 위쪽 값을 참조해 집합을 생성합니다.

2. 즉 현재 위치가 x, y일 때 현재 위치와 상호작용이 가능한 위치는 {x - 1, y}와 {x, y - 1}의 두개의 위치입니다.

3. 만약 해당 두 위치가 현재 위치와 서로 연결되어있다면, 두 위치는 현재 위치를 매개로 같은 집합이 이루어집니다.

4. 순회를 마쳤을 때, 모든 벽이 아닌 공간은 집합이 되어있으므로 벽을 부쉈을 경우 상하좌우의 집합의 갯수를 모두 세어줍니다.

 

---

 

코드

#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

vector<int> par;
map<int, int> szmap;
vector<vector<char>> grp;

int find(int x) {
	if (par[x] == x) return x;
	if (par[x] == -1) return -1;
	return par[x] = find(par[x]);
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return ;
	par[b] = a;
	szmap[a] += szmap[b];
}

int main() {
	int n, m; cin >> n >> m;
	par.resize(n * m, -1);
	grp.resize(n, vector<char>(m));
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			cin >> grp[i][j];
			if (grp[i][j] == '0') {
				szmap[i * m + j] = 1;
				par[i * m + j] = i * m + j;
				if (i - 1 >= 0 && grp[i - 1][j] == '0')
					merge((i - 1) * m + j, i * m + j);
				if (j - 1 >= 0 && grp[i][j - 1] == '0')
					merge(i * m + j - 1, i * m + j);
			}
		}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (grp[i][j] == '0') cout << 0;
			else {
				set<int> tmp;
				for (int k = 0; k < 4; ++k) {
					int nY = i + dy[k];
					int nX = j + dx[k];
					if (nY < 0 || nX < 0 || nY >= n || nX >= m) continue ;
					tmp.insert(find(nY * m + nX));
				}
				int res = 1;
				for (auto t : tmp)
					if (t == -1) continue;
					else res += szmap[t];
				cout << res % 10;
			}
		}
		cout << '\n';
	}
	return 0;
}

 

시간 복잡도

O(NM logNM)

NM 크기의 배열을 순회하며 O(logNM) 만큼의 시간복잡도를 가지는 find 연산을 수행하기에 위와 같은 시간복잡도가 발생합니다.

 

---

그래프 탐색을 통한 코드보다 빠르지 않지만 더 간단한 자료구조로 해결할 수 있는 코드였습니다.

해당 방법으로 푼 풀이는 찾아봐도 안 나와서 참고하시라고 포스팅합니다.