문제 간략 설명

벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 센다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

풀이 방법

  1. 맵을 순회하면서 이어진 이동할 수 있는 곳을 queue에 담아 놓는다.
  2. queue 크기만큼 cnt_map에 저장하고, id를 활용한다.
  3. 다시 맵을 순회하면서 벽이면 상하좌우 id가 동일하지 않은 cnt_map 크기만큼 더해서 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, M, id;

vector<string> input_map;
queue<pair<int, int>> q;
pair<int, int> cnt_map[1000][1000];

void dfs(int y, int x)
{
	if (x < 0 || x >= M || y < 0 || y >= N ||
		input_map[y][x] != '0')
		return;

	q.push({y, x});
	input_map[y][x] = '2';
	dfs(y - 1, x);
	dfs(y + 1, x);
	dfs(y, x - 1);
	dfs(y, x + 1);
}

void cal_res(int y, int x, int* sum, vector<int>& ids)
{
	if (x < 0 || x >= M || y < 0 || y >= N ||
		input_map[y][x] == '1')
		return;
	
	int id = cnt_map[y][x].second;

	if (find(ids.begin(), ids.end(), id) != ids.end())
		return;
	
	ids.push_back(id);
	*sum += cnt_map[y][x].first;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		string str;

		cin >> str;

		input_map.push_back(str);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (input_map[i][j] == '0') {
				dfs(i, j);
				int cnt = q.size();
				while (!q.empty()) {
					pair<int, int> p = q.front();
					cnt_map[p.first][p.second].first = cnt;
					cnt_map[p.first][p.second].second = id;
					q.pop();
				}
				id++;
			}
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (input_map[i][j] != '1') {
				cout << '0';
				continue;
			}

			int sum = 1;
			vector<int> ids;

			cal_res(i - 1, j, &sum, ids);
			cal_res(i + 1, j, &sum, ids);
			cal_res(i, j - 1, &sum, ids);
			cal_res(i, j + 1, &sum, ids);

			cout << sum % 10;
		}
		cout << endl;
	}

	return 0;
}

Key Points