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

📌 문제

BOJ 바로가기

🔍 풀이

📍 0이 있는 곳에 BFS를 돌려서 0 뭉텅이마다 라벨링을 해줬다. 동시에 뭉텅이를 구성하는 0이 몇 개인지도 벡터에 담아주었다.

📍 이후 1의 상하좌우에 0이 있다면 뭉텅이의 개수를 ans[i][j]에 더해주었다.

📍 이 때 같은 뭉텅이가 두 번 이상 나오는 경우에 중복해서 더해주면 안 되므로, 일단 set에 넣어준 후 마지막에 개수를 한꺼번에 더해주는 방식으로 진행하였다.

🥶 처음엔 간단한 문제인 줄 알고 풀었다. 단순하게 BFS를 이용해 갈 수 있는 곳의 개수를 알아내면 되는 문제인 줄 알았는데, 그렇게 푸니까 시간초과가 발생했다. 배열의 크기가 최대 1000*1000까지 커질 수 있기 때문이었다..

🚩 정답 소스코드

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

int n, m, nbr = 1, map[1001][1001], numbering[1001][1001], ans[1001][1001] = { 0, };
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<int> zero_size;

void bfs(int x, int y){
	queue<pair<int,int>> q;
	int cnt = 0; // 0 개수
	q.push({x, y});
	numbering[x][y] = nbr; 
	cnt++;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && numbering[nx][ny] == 0 && map[nx][ny] == 0){
				q.push({nx, ny});
				numbering[nx][ny] = nbr;
				cnt++;
			}
		}
	}
	zero_size.push_back(cnt); // 그룹당 0 개수를 벡터에 넣어주기
	nbr++; // 그룹 번호 (1번부터 시작)
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);
	// 0인 그룹 넘버링
	zero_size.push_back(0); // 1번부터 넘버링 시작하니까 벡터도 한칸 밀어주기
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++){
			if (map[i][j] == 0 && numbering[i][j] == 0)
				bfs(i, j);
		}
	}
	// 상하좌우에서 갈 수 있는 영역 개수 체크해서 ans 배열에 넣기
	set<int> s; // 같은 그룹을 중복해서 방문하지 않기 위해 set 사용
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if (map[i][j] == 0) continue;
			ans[i][j] = 1; // 자기 자신 영역 포함
			for(int k = 0; k < 4; k++){
				int x = i + dx[k];
				int y = j + dy[k];
				if (0 <= x && x < n && 0 <= y && y < m && numbering[x][y] != 0)
					s.insert(numbering[x][y]);
			}
			for(auto a : s)
				ans[i][j] += zero_size[a];
			s.clear();
		}
	}
	// 출력
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++)
			printf("%d", ans[i][j] % 10);
		printf("\n");
	}
	return 0;
}

🚩 시간초과 소스코드

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

int n, m, map[1000][1000], ans[1000][1000];
bool visited[1000][1000];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int bfs(int x, int y){
	queue<pair<int,int>> q;
	int cnt = 0;
	q.push({x, y});
	visited[x][y] = true;
	cnt++;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !visited[nx][ny] && map[nx][ny] == 0){
				q.push({nx, ny});
				visited[nx][ny] = true;
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++){
			if (map[i][j] == 0){
				ans[i][j] = 0;
				continue;
			}
			memset(visited, false, sizeof(visited));
			ans[i][j] = bfs(i, j);
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++)
			printf("%d", ans[i][j] % 10);
		printf("\n");
	}
}