백준 16946 - 벽 부수고 이동하기 4

문제 설명

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 모든 벽에 대해 해당 벽을 부수었을 때 이동할 수 있는 칸의 개수를 구해야 한다.

 

간단하게 생각해보면, 모든 벽에 대해 bfs를 통해 이동할 수 있는 칸을 세면 된다.

하지만, 이렇게 진행하면 다른 벽이지만 이미 방문한 칸을 방문하게 되면 문제가 발생한다.

따라서, 이를 구분할 방법이 필요하다.

 

여러 방법이 있겠지만, 각 칸에 대한 bfs를 진행하여 그룹을 만드는 방법을 선택했다.

그룹을 만들어 놓고 해당 그룹이 어떠한 사이즈를 갖는지 bfs과정에서 계산하여 기록하였다.

이후, 모든 벽에 대해 인접한 칸에 어떠한 그룹이 존재하는지 살펴본 후, 그룹의 사이즈를 더해주었다.

신경 써야 할 부분은 어떠한 벽이 같은 그룹의 블록으로 둘러싸여 있을 수 있다.

그렇게 되면 동일한 그룹을 여러 번 카운팅 하기 때문에 문제가 발생한다.

따라서, set과 같은 자료구조를 통해 유일한 그룹으로 관리를 해야 한다.

또한, 이동할 수 있는 모든 칸을 세야하기 때문에 벽을 부신 현재 칸을 포함한 결과를 출력해야 한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<vector<int>> board;
vector<vector<int>> dp;
vector<int> sizes;
vector<vector<bool>> visited;

vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };

void Bfs(int i, int j, int idx)
{
	queue<pair<int, int>> q;
	q.push({ i,j });
	int size = 0;

	while (!q.empty())
	{
		auto [y, x] = q.front();
		q.pop();

		if (visited[y][x]) continue;
		visited[y][x] = true;
		size++;
		dp[y][x] = idx;

		for (int i = 0; i < 4; i++)
		{
			int newY = y + dy[i];
			int newX = x + dx[i];

			if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue;
			if (visited[newY][newX]) continue;
			if (board[newY][newX] == 1) continue;

			q.push({ newY,newX });
		}
	}

	sizes.push_back(size);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> N >> M;
	board.resize(N, vector<int>(M));
	dp.resize(N, vector<int>(M, 0));
	visited.resize(N, vector<bool>(M, false));
	sizes.push_back(-1);

	for (int i = 0; i < N; i++)
	{
		string input;
		cin >> input;
		for (int j = 0; j < M; j++)
		{
			board[i][j] = input[j] - '0';
		}
	}

	//덩어리 만들고 상하좌우 더하기
	int idx = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (visited[i][j]) continue;
			if (board[i][j] == 1) continue;
			Bfs(i, j, idx++);
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] == 0)
			{
				cout << 0;
				continue;
			}

			unordered_set<int> near;
			int ans = 0;
			for (int k = 0; k < 4; k++)
			{
				int newY = i + dy[k];
				int newX = j + dx[k];

				if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue;
				if (dp[newY][newX] == 0) continue;

				near.insert(dp[newY][newX]);
			}

			for (auto nearBlock : near)
			{
				ans += sizes[nearBlock];
			}

			cout << (ans + 1) % 10;
		}

		cout << "\n";
	}

	return 0;
}

---