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

1. 문제

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

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

 

2. 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

3. 소스 코드

#include <iostream>
#include <queue>
#include <string>
#include <set>
#define MAX_N 1000
#define MAX_M 1000

using namespace std;

int N, M;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = { 0, 1, 0, -1 };
int group[MAX_N * MAX_M];
int map[MAX_N][MAX_M];
int ans[MAX_N][MAX_M];

// BFS 알고리즘
void bfs(int y, int x, int group_idx)
{
	int ret = 1;
	queue<pair<int,int>> q;
	q.push({ y, x });
	map[y][x] = group_idx;

	// Queue가 빌때까지 탐색
	while (!q.empty()) {
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();

		// 상하좌우 탐색
		for (int i = 0; i < 4; i++) {
			int next_y = cur_y + dy[i];
			int next_x = cur_x + dx[i];

			if (next_y < 0 || next_y >= N || next_x < 0 || next_x >= M) continue;	// 맵 벗어났을 경우, Skip
			if (map[next_y][next_x] != 0) continue;	// 값이 0이 아닌 경우, Skip

			ret++;	// 탐색한 위치 갯수 더하기
			map[next_y][next_x] = group_idx;	// 그룹 인덱스 입력
			q.push({ next_y, next_x });
		}
	}

	group[group_idx] = ret % 10;	// 해당 그룹의 갯수 입력
}

int main()
{
	// I/O 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N X M 맵 크기 입력
	cin >> N >> M;

	// 맵 정보 입력
	for (int y = 0; y < N; y++) {
		string row;
		cin >> row;

		for (int x = 0; x < M; x++)
			map[y][x] = row[x] - '0';
	}

	// BFS 알고리즘
	// 맵에서 0인 부분들 그룹으로 묶기
	int group_idx = 2;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] != 0) continue;	// 값이 0이 아닌 경우, Skip

			// BFS 알고리즘
			bfs(y, x, group_idx++);
		}
	}

	// 맵에서 1인 위치에서 상하좌우 인접한 위치 파악
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] != 1) continue;	// 값이 1이 아닌 경우, Skip

			set<int> groups;

			// 상하좌우 인접한 위치 파악
			for (int i = 0; i < 4; i++) {
				int next_y = y + dy[i];
				int next_x = x + dx[i];

				if (next_y < 0 || next_y >= N || next_x < 0 || next_x >= M) continue;	// 맵에서 벗어난 경우, Skip
				if (map[next_y][next_x] == 1) continue;	// 값이 1인 경우, Skip

				// 해당 위치의 그룹 인덱스 추가
				int group_idx = map[next_y][next_x];
				groups.insert(group_idx);
			}

			// 찾아낸 그룹 인덱스들을 바탕으로 각 그룹의 갯수들 더하기
			int cnt = 1;
			set<int>::iterator iter;
			for (iter = groups.begin(); iter != groups.end(); iter++)
				cnt += group[*iter];

			ans[y][x] = cnt % 10;	// 10으로 나눈 나머지 입력
		}
	}

	// 정답 출력
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++)
			cout << ans[y][x];
		
		cout << '\n';
	}

	return 0;
}

 

4. 유용한 알고리즘

1) BFS(너비 우선 탐색)

// BFS 알고리즘
void bfs(int y, int x, int group_idx)
{
	int ret = 1;
	queue<pair<int,int>> q;
	q.push({ y, x });
	map[y][x] = group_idx;

	// Queue가 빌때까지 탐색
	while (!q.empty()) {
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();

		// 상하좌우 탐색
		for (int i = 0; i < 4; i++) {
			int next_y = cur_y + dy[i];
			int next_x = cur_x + dx[i];

			if (next_y < 0 || next_y >= N || next_x < 0 || next_x >= M) continue;	// 맵 벗어났을 경우, Skip
			if (map[next_y][next_x] != 0) continue;	// 값이 0이 아닌 경우, Skip

			ret++;	// 탐색한 위치 갯수 더하기
			map[next_y][next_x] = group_idx;	// 그룹 인덱스 입력
			q.push({ next_y, next_x });
		}
	}

	group[group_idx] = ret % 10;	// 해당 그룹의 갯수 입력
}