백준 16946번 | 벽 부수고 이동하기 4 (C++ 풀이)

  문제  

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

16946번: 벽 부수고 이동하기 4

---

  풀이  

• 사용 알고리즘 : DFS
• 시간 복잡도 : O(N^2)

문제의 해석은 어렵지 않으나, 시간 복잡도를 잘 생각해보며 풀어야합니다.

 

Naive한 풀이는 이렇습니다.모든 벽인 칸에 대해서 BFS를 돌려 이동할 수 있는 칸의 개수를 구해주면 됩니다. 하지만 시간 복잡도가 너무 크죠.단순히 BFS 한 번 돌리는 데 발생하는 시간은 O(N^2)이 될 겁니다. 여기서 문제는 매 번 돌릴때마다 방문 배열을 초기화해야 하므로 최종 시간 복잡도는 O(N^4)가 되므로 이 방법으로는 풀 수 없습니다.

 

그렇다면 벽이 아닌 칸이 속한 컴포넌트 영역을 미리 구해놓는다면 어떨까요?

각각의 컴포넌트에 고유한 숫자를 매칭시켜주고, 각 컴포넌트들의 크기를 미리 구해놓는다면 이 문제를 쉽게 풀 수 있습니다.컴포넌트를 전처리 한 후에, 벽인 칸 A에 대해서 상하좌우 인접한 칸만 봅니다. 그렇다면 A에서 갈 수 있는 칸의 개수는, A에 인접한 각 컴포넌트들의 크기의 합이 되겠죠.

 

이렇게 풀었을 때의 시간 복잡도는, 컴포넌트를 구하는 데에 O(N^2), 그리고 모든 벽인 칸에 대해서 상하좌우 인접한 칸만 보면 되므로 O(4 * N^2), 따라서 최종 시간 복잡도는 O(N^2)이 됩니다.

---

  코드  

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;

int mmap[1001][1001];
bool visited[1001][1001];
int componentCnt[1000001];
int componentNode[1001][1001];
int dx[4] = {1, -1 ,0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m;
int node = 0, cnt;

void dfs(int x, int y) {
	visited[x][y] = true;
	componentNode[x][y] = node;
	cnt++;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		if (visited[nx][ny] || mmap[nx][ny] == 1) continue;
		dfs(nx, ny);
	}
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			mmap[i][j] = s[j] -'0';
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visited[i][j] || mmap[i][j] == 1) continue;
			cnt = 0;
			node++;
			dfs(i, j);
			componentCnt[node] = cnt;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (mmap[i][j] == 0) continue;
			set<int> visitedSet;
			int tmp = 1;
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (mmap[nx][ny] != 0 || visitedSet.count(componentNode[nx][ny])) continue;
				visitedSet.insert(componentNode[nx][ny]);
				tmp += componentCnt[componentNode[nx][ny]];
			}
			mmap[i][j] = tmp % 10;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << mmap[i][j];
		}
		cout << '\n';
	}
	return 0;
}