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

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

문제

---

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

 

입력

---

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

 

출력

---

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

 

문제 풀이

---

그래프 탐색 문제.

 

한 칸마다 일반적인 그래프 탐색 후 초기화하는 방식으로 진행하면 시간초과가 발생한다. 따라서 반복적인 탐색이 발생하지 않게 빈 곳을 탐색할 때 한 번의 그래프 탐색으로 만들어지는 하나의 구역을 저장한 후, 벽인 곳은 자기 자신과 구역에 존재하는 칸의 수를 더해주도록 구현한다.

먼저 빈 칸인 곳을 일반적인 그래프 탐색으로 진행하되, 탐색을 시작한 첫 위치와, 이동할 수 있는 칸의 개수를 저장하는 배열을 만든다. 큐나 스택에 원소를 넣으면서 탐색을 시작한 첫 위치를 넣는 배열의 해당 칸에 첫 위치를 넣어준다. 탐색이 종료되면 이동할 수 있는 칸의 개수를 저장하는 배열에 해당 구역의 몇개의 칸으로 이루어져 있는지를 저장해둔다.

이제 벽인 곳이, 해당 칸을 포함하여 몇 개의 칸을 이동할 수 있는지 구한다. 이는 상하좌우 4칸의 구역의 칸 수를 더해주면 된다. 상하좌우 중 일부는 같은 구역일 수 있으므로 set을 이용하여 겹치지 않는 시작지점만을 얻어내고, set 전체를 탐색하여 한 구역의 칸 수가 몇 개인지 얻어내면 된다.

 

아래는 코드.

#include <iostream>
#include <queue>
#include <utility>
#include <set>
using namespace std;
int N, M;
char** map;
bool** isVisited;
pair<int, int>** startPoint;
int** countRecord;

queue<pair<int, int>> bfsQueue;
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };

void bfs(int x, int y)
{
	isVisited[x][y] = true;
	bfsQueue.push(pair(x, y));
	int count = 0;
	while (!bfsQueue.empty())
	{
		pair<int, int> current = bfsQueue.front();
		for (int i = 0; i < 4; i++)
		{
			int nextX = current.first + dx[i];
			int nextY = current.second + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && isVisited[nextX][nextY] == false && map[nextX][nextY] == '0')
			{
				isVisited[nextX][nextY] = true;
				bfsQueue.push(pair(nextX, nextY));
				startPoint[nextX][nextY].first = x;
				startPoint[nextX][nextY].second = y;
			}
		}
		bfsQueue.pop();
		count++;
	}
	countRecord[x][y] = count;
}

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

	cin >> N >> M;
	map = new char*[N];
	isVisited = new bool*[N];
	startPoint = new pair<int, int>*[N];
	countRecord = new int*[N];
	for (int i = 0; i < N; i++)
	{
		map[i] = new char[M];
		isVisited[i] = new bool[M];
		startPoint[i] = new pair<int, int>[M];
		countRecord[i] = new int[M];
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
			isVisited[i][j] = false;
			startPoint[i][j] = pair(i, j);
			countRecord[i][j] = 0;
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (isVisited[i][j] == false && map[i][j] == '0')
			{
				bfs(i, j);
			}
		}
	}
	set<pair<int, int>> s;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			s.clear();
			if (map[i][j] == '1')
			{
				countRecord[i][j] = 1;
				for (int k = 0; k < 4; k++)
				{
					int nextX = i + dx[k];
					int nextY = j + dy[k];
					if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && map[nextX][nextY] == '0')
					{
						s.insert(startPoint[nextX][nextY]);
					}
				}
				for (set<pair<int, int>>::iterator it = s.begin(); it != s.end(); it++ )
				{
					countRecord[i][j] += countRecord[it->first][it->second];
				}
				cout << countRecord[i][j] % 10;
			}
			else
			{
				cout << "0";
			}
		}
		cout << "\n";
	}
	return 0;
}