[백준/BOJ] 백준 16946번 : 벽 부수고 이동하기 4

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

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

 

맵에서 0으로 표시된 위치들 중 인접한 구역들을 하나로 공간으로 묶어서 공간 id로 부여하고, 공간 id의 크기를 저장한다. 그리고 벽인 위치들을 확인하며 해당 벽의 인접한 공간 id들을 확인하고 그 공간 id들의 크기와 해당 벽의 위치까지 고려하여 문제를 해결했다.

 

코드

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

int n, m;
vector<string> board;
int id_cnt = 0;
int check[1000][1000]; //해당 위치가 어떤 공간인지 저장
vector<int> id_size(1000001, 0); //해당 공간의 크기 저장
int result[1000][1000];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void Pre()
{
	for (int i = 0; i < 1000; i++)
		for (int j = 0; j < 1000; j++)
		{
			check[i][j] = 0;
			result[i][j] = 0;
		}
}

//dfs를 하며 here을 id로 체크한다
void Dfs(pair<int, int> here, int id)
{
	check[here.first][here.second] = id;

	for (int dir = 0; dir < 4; dir++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] == '0' && check[there.first][there.second] == 0)
			Dfs(there, id);
	}

}

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

	Pre();

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == '0' && check[i][j] == 0)
			{
				id_cnt++;
				Dfs(make_pair(i, j), id_cnt);
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == '0')
				id_size[check[i][j]]++; //해당 공간의 크기 추가
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//벽일때
			if (board[i][j] != '0')
			{
				pair<int, int> here = make_pair(i, j);

				//해당 벽에 인접해있는 공간들의 id를 저장
				set<int> side_id;
				for (int dir = 0; dir < 4; dir++)
				{
					pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

					if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] == '0' && check[there.first][there.second] != 0)
					{
						side_id.insert(check[there.first][there.second]);
					}
				}

				for (set<int>::iterator it = side_id.begin(); it != side_id.end(); it++)
				{
					result[here.first][here.second] = (result[here.first][here.second] + id_size[*it]) % 10;
				}
				result[here.first][here.second] = (result[here.first][here.second] + 1) % 10; //현재위치
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cout << result[i][j];
		cout << "\n";
	}

	return 0;
}