[백준 C++] 16946 벽 부수고 이동하기 4 - 너비우선탐색

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

#include <iostream>
#include <string>
#include <queue>
using namespace std;

const int DX[4] = { -1, 0, 1, 0 };
const int DY[4] = { 0, -1, 0, 1 };

int N, M;
bool Wall[1000][1000];
bool Visited[1000][1000];

int Area[1000][1000];
int AreaSize[1000000];

int BFS(int AreaNum, int SRow, int SCol)
{
	queue<pair<int, int>> SQ;
	SQ.emplace(SRow, SCol);
	Visited[SRow][SCol] = true;
	Area[SRow][SCol] = AreaNum;

	int Cnt = 1;
	while (!SQ.empty())
	{
		int R = SQ.front().first;
		int C = SQ.front().second;
		SQ.pop();

		for (int i = 0; i < 4; ++i)
		{
			int NR = R + DY[i];
			int NC = C + DX[i];
			if (NR < 0 || NR > N - 1
				|| NC < 0 || NC > M - 1
				|| Wall[NR][NC]
				|| Visited[NR][NC])
			{
				continue;
			}

			Visited[NR][NC] = true;
			Area[NR][NC] = AreaNum;
			SQ.emplace(NR, NC);
			++Cnt;
		}
	}

	return Cnt;
}

int Counting(int Row, int Col)
{
	int Cnt = 1;
	int AreaNum[4] = {};
	for (int i = 0; i < 4; ++i)
	{
		int NR = Row + DY[i];
		int NC = Col + DX[i];
		if (NR < 0 || NR > N - 1
			|| NC < 0 || NC > M - 1
			|| Wall[NR][NC])
		{
			continue;
		}

		bool bSameArea = false;
		int AN = Area[NR][NC];
		for (int j = 0; j < i; ++j)
		{
			if (AN == AreaNum[j])
			{
				bSameArea = true;
			}
		}

		if (!bSameArea)
		{
			AreaNum[i] = AN;
			Cnt += AreaSize[AN];
		}
	}

	return Cnt;
}

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

	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		string Str;
		cin >> Str;

		for (int j = 0; j < M; ++j)
		{
			int Num = Str[j] - '0';
			Wall[i][j] = Num;
		}
	}

	int AreaNum = 1;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (!Wall[i][j] && !Visited[i][j])
			{
				AreaSize[AreaNum] = BFS(AreaNum, i, j);
				++AreaNum;
			}
		}
	}

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			int Cnt = (Wall[i][j]) ? Counting(i, j) : 0;
			cout << Cnt % 10;
		}
		cout << '\n';
	}
}

---

 

너비 우선 탐색을 이용해서 푸는 문제입니다.

 

DFS를 이용해서 벽이 없는 인접한 칸끼리 같은 영역으로 묶고,

해당 영역의 크기를 저장해주는 방식으로 풀면 됩니다.

 

모든 벽이 없는 영역의 번호와 크기가 매겨졌다면

각 벽 칸에 대해서 해당 칸과 인접한 빈 영역들의 크기를 더해주고 10으로 나눈 나머지를 출력해줍니다.

 

인접한 빈 영역의 크기를 더해줄 때는 이미 더한 영역 중 중복되는 번호의 영역이 없는지 체크해주어야 합니다.