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

벽 부수고 이동하기 4 (백준 16946번)

 

dfs/bfs 기반으로 발상만 잘하면 쉽게 풀 수 있는 문제

 

풀이 과정

1. 먼저 빈 공간들을 분리하여 크기를 구한다(find 함수).
   • vi 배열로 visit 체크해주는 동시에, 각 빈 공간들이 어떤 집합에 속했는지(set_num) 저장
   • set_cnt 배열에 각 집합마다 빈 공간의 크기를 저장
2. 이후, 벽마다 상하좌우에 빈 공간이 있다면 해당 공간이 속한 집합의 빈 공간 크기(set_cnt)를 불러와 해당 벽이 부서졌을 때 만들어질 공간 크기(hap)에 저장한 후 출력한다(get 함수).
   • 빈 공간끼리 같은 집합에 속할 수 있기 때문에, set_vi 배열로 집합끼리 visit 체크를 해주어야 함
   • hap % 10으로 출력할 것

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;

int n, m, cnt, set_num = 1;
char d[1001][1001];
int dir[2][4] = { {1, 0, -1, 0}, {0, 1, 0, -1} }, vi[1001][1001];
int set_cnt[1'000'001], set_vi[1'000'001];

void find(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int new_x = x + dir[1][i], new_y = y + dir[0][i];
		if (new_x < 0 || new_x >= m || new_y < 0 || new_y >= n)continue;
		if (vi[new_y][new_x])continue;
		if (d[new_y][new_x] == '0') {
			cnt++;
			vi[new_y][new_x] = set_num;
			find(new_x, new_y);
		}
	}
	return;
}

int get(int x, int y) {
	cnt = 0;
	stack<int> st;
	for (int i = 0; i < 4; i++) {
		int new_x = x + dir[1][i], new_y = y + dir[0][i];
		if (new_x < 0 || new_x >= m || new_y < 0 || new_y >= n)continue;
		if (d[new_y][new_x] == '0' && set_vi[vi[new_y][new_x]] == 0) {
			set_vi[vi[new_y][new_x]] = 1;
			cnt += set_cnt[vi[new_y][new_x]];
			st.push(vi[new_y][new_x]);
		}
	}
	while (!st.empty()) {
		set_vi[st.top()] = 0;
		st.pop();
	}
	return cnt;
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)scanf("%s", d[i]);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (d[i][j] == '0' && vi[i][j] == 0) {
				vi[i][j] = set_num;
				cnt = 1;
				find(j, i);
				set_cnt[set_num++] = cnt;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int hap = 1;
			if (d[i][j] == '1') {
				hap += get(j, i);
				printf("%d", hap % 10);
			}
			else printf("0");
		}
		printf("\n");
	}
	return 0;
}