[BOJ]16946번: 벽 부수고 이동하기 4 (c++)

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

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

 

bfs + 인접 빈칸 영역을 그룹화하여, 그 개수를 따로 저장하기

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

struct pos {
	int x, y;
};

int N, M;
int dr_x[] = { 0, 1, 0, -1 };
int dr_y[] = { 1, 0, -1, 0 };
const int MAX = 1000;
char map[MAX][MAX + 1];
int group[MAX][MAX];

int bfs(pos strt, int idx)
{
	// 큐에 시작지점 push 및 group에 idx값 저장
	queue<pos> q;
	q.push(strt);
	group[strt.x][strt.y] = idx;

	int cnt = 1;
	while (!q.empty())
	{
		pos p = q.front();
		q.pop();

		// 4방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int nx = p.x + dr_x[i];
			int ny = p.y + dr_y[i];

			// 범위를 넘어서면 continue
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
			{
				continue;
			}

			// 다음 영역이 빈칸이고 아직 group에 인덱스를 매기지 않았다면
			if (map[nx][ny] == '0' && group[nx][ny] == 0)
			{
				++cnt;
				group[nx][ny] = idx;
				q.push({nx, ny});
			}
		}
	}
	// 해당 빈칸그룹의 영역크기 반환
	return cnt;
}

void plus_adj_group(vector<int> &cnts, pos p)
{
	set<int> s;
	// 4방향 탐색
	for (int k = 0; k < 4; ++k)
	{
		int nx = p.x + dr_x[k];
		int ny = p.y + dr_y[k];

		// 범위를 넘어서면 continue
		if (nx < 0 || nx >= N || ny < 0 || ny >= M)
		{
			continue;
		}

		// 인접 영역이 빈칸이면 set에 그룹 인덱스 push (중복 방지)
		if (map[nx][ny] == '0')
		{
			s.insert(group[nx][ny]);
		}
	}

	// 인접한 빈칸그룹 인덱스의 영역크기 더하기
	int num = 1;
	for (int idx : s)
	{
		num += cnts[idx];
	}
	num %= 10;

	map[p.x][p.y] = num + '0';
}

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

	// 입력
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		cin >> map[i];
	}

	/*
		Flood Fill
		cnts 배열에 각 빈칸 그룹의 연결된 영역 크기를 순서대로 저장
	*/
	vector<int> cnts(1);
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			// map[i][j]이 빈칸이고 group에 인덱스가 매겨지지 않았으면
			if (map[i][j] == '0' && group[i][j] == 0)
			{
				// bfs로 group배열에 인덱스를 저장 후, cnts배열에 영역크기 저장
				cnts.push_back(bfs({i, j}, cnts.size()));
			}
		}
	}

	// map[i][j]이 벽이면, 인접한 빈칸그룹의 영역크기를 더한다
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (map[i][j] == '1')
			{
				plus_adj_group(cnts, {i, j});
			}
		}
	}

	// 출력
	for (int i = 0; i < N; ++i)
	{
		cout << map[i] << '\n';
	}

	return 0;
}

 

 

Flood Fill이라는 개념을 처음 배웠다. 

이 문제는 <인접 영역>을 공부하게 해주었다.

참고 블로그 : https://blog.encrypted.gg/941

[실전 알고리즘] 0x09강 - BFS

 

 

각각의 벽에 대해서 다음을 구해보려고 한다.
· 벽을 부수고 이동할 수 있는 곳으로 변경한다.
· 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

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

 

입력 map이 주어지면

벽으로부터 이동할 수 있는 빈칸 영역의 개수를 

다시 map형태로 출력하는 문제이다.

 

 

여기서 아주 단순하게

각각의 벽으로부터 뻗어갈 수 있는 빈칸영역을 일일이 다 bfs탐색 해볼까^^

하면 당연히 시간초과가 난다.

아래처럼 빈칸 영역이 모두 연결되어 있다면 최악의 경우 O(N*M*N*M)의 시간복잡도가 된다

// input
6 6
101010
000000
101010
000000
101010
000000

// output
808080
000000
808080
000000
808080
000000

알면서도 괜히 한번 해봤고.. 역시 시간초과가 났다ㅋㅋㅋ

 

 

그렇다면 연결되어 있는 빈칸들의 개수를

미리 저장해둘 group_map이 따로 필요하다는 결론이 난다.

과정은 2단계로 나뉜다.

1. 하나로 연결된 빈칸그룹에 인덱스를 매겨 구분지어야 한다.  --> Flood Fill

2. 해당 빈칸 그룹의 영역크기를 저장해야 한다. 

/*
	Flood Fill
	cnts 배열에 각 빈칸 그룹의 연결된 영역 크기를 순서대로 저장
*/
vector<int> cnts(1);
for (int i = 0; i < N; ++i)
{
	for (int j = 0; j < M; ++j)
	{
		// map[i][j]이 빈칸이고 group에 인덱스가 매겨지지 않았으면
		if (map[i][j] == '0' && group[i][j] == 0)
		{
			// 1. bfs로 group배열에 인덱스를 저장
			int group_size = bfs({i, j}, cnts.size());

			// 2. cnts배열에 영역크기 저장
			cnts.push_back(group_size);
		}
	}
}

 

 

 

그리고 다시 map을 탐색하면서 map[x][y]가 벽이면

인접영역이 빈칸일 경우 map[x][y]에 해당 영역의 크기를 더한다.

...

	// 인접 영역이 빈칸이면 set에 그룹 인덱스 push (중복 방지)
	if (map[nx][ny] == '0')
	{
		s.insert(group[nx][ny]);
	}
}

// 인접한 빈칸그룹 인덱스의 영역크기 더하기
int num = 1;
for (int idx : s)
{
	num += cnts[idx];
}
num %= 10;

map[p.x][p.y] = num + '0';

 

 

끝!