[C++] BOJ(백준) 16946 벽 부수고 이동하기 4

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

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

 

BFS 문제다.

 

벽에서 갈 수 있는 칸들을 세는 문제다.

모든 벽에서 BFS를 돌리면 빈 칸을 여러 번 방문하기 때문에 시간초과가 날 것이다.

빈 칸의 영역을 찾아서 크기를 구한 뒤 배열에 저장해뒀다.

 

그 후 배열을 전체 탐색 하면서 벽인 경우 4방향을 검사해 갈 수 있는 영역의 크기를 더했다.

이 때 이어져 있는 영역이 존재할 수 있으므로, 영역을 찾을 때 영역의 번호를 부여했다.

영역의 번호가 같은 경우는 카운트 하지 않는다.

 

이런 방법을 썼음에도 나는 시간초과가 났는데, 그 이유는 영역에 대한 정보를 배열에 저장할 때

방문 배열로 현재 영역을 저장하고 배열을 전체 탐색하면서 영역 정보를 저장해나갔다.

이러면 시간이 너무 오래 걸리므로 영역 칸들을 큐에 넣어두고 BFS 종료 후 해당 칸 들을 꺼내면서 저장했다.

 

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

int n, m, tmp;
int arr[1000][1000];
int visit[1000][1000];
int idx[1000][1000];

int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

void bfs(int index, int r, int c) {
	queue<pair<int, int>> q;
	queue<pair<int, int>> pos;

	pos.push({ r, c });
	q.push({ r, c });
	visit[r][c] = -2;

	int cnt = 1;
	while (!q.empty()) {
		int rr = q.front().first;
		int cc = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nr = rr + dr[i];
			int nc = cc + dc[i];

			if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
			if (visit[nr][nc] != 0) continue;
			if (arr[nr][nc] == -1) continue;

			q.push({ nr, nc });
			pos.push({ nr, nc });
			visit[nr][nc] = -2;

			cnt++;
		}
	}

	while (!pos.empty()) {
		int rr = pos.front().first;
		int cc = pos.front().second;
		pos.pop();

		visit[rr][cc] = cnt;
		idx[rr][cc] = index;
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;	cin >> s;
		for (int j = 0; j < m; j++) {
			arr[i][j] = s[j] - '0';
			if (arr[i][j] == 1) {
				arr[i][j] = -1;
				visit[i][j] = -1;
			}
		}
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (visit[i][j] == 0) 
				bfs(++tmp, i, j);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) cout << 0;
			else {
				int cnt = 1;
				int temp[4];
				int ind = 0;
				for (int k = 0; k < 4; k++) {
					int nr = i + dr[k];
					int nc = j + dc[k];

					if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
					if (visit[nr][nc] == -1) continue;
					
					temp[ind++] = idx[nr][nc];

					for (int kk = 0; kk < ind - 1; kk++) 
						if (temp[kk] == idx[nr][nc]) {
							cnt -= visit[nr][nc];
							break;
						}

					cnt += visit[nr][nc];
				}

				cout << cnt % 10;
			}
		}
		cout << "\n";
	}
}