백준 16946 벽 부수고 이동하기 4 (c++) : 피너클

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

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

귀찮은 bfs문제다.

cin >> n >> m;
memset(num, 0, sizeof(num));
memset(visited, false, sizeof(visited));
for (int i = 0; i < n; i++) {
	cin >> map[i];
	for (int j = 0; j < m; j++) {
		if (map[i][j] != '0') num[i][j] = 1;
	}
}

값들을 입력받고 num과 visited를 초기화한다.

그후 map[i][j]가 0이 아니라면 벽이라는 뜻이니 num[i][j]을 1로 바꾼다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (map[i][j] == '0' && !visited[i][j]) {
			bfs(i, j);
		}
	}
}

그후 반복문을 돌며 map[i]j[j]이 0이고 아직 방문하지 않은 공간이라면 bfs를 돌린다.

 

2번 예제를 통해 bfs의 작동원리를 확인해보겠다.

1	1	0	0	1
0	0	1	1	1
0	1	0	1	0
1	0	1	0	1

map[i][j]에서 0인 부분주위에 이동할수있는 모든 부분을 돌아본다.

1	1	0	0	1
0	0	1	1	1
0	1	0	1	0
1	0	1	0	1

파란색 부분은 총 3부분이니 int ans에 3을 집어넣는다.

1	1	0	0	1
0	0	1	1	1
0	1	0	1	0
1	0	1	0	1

그후 num배열을 업데이트한다. 파란색 부분 주위에 벽에 ans값인 3을 더할것이다.

4	4	0	0	1
0	0	4	1	1
0	4	0	1	0
4	0	1	0	1

이걸 계속해서 반복한다.

4	4	0	0	1
0	0	4	1	1
0	4	0	1	0
4	0	1	0	1

ans = 2

4	6	0	0	3
0	0	6	3	1
0	4	0	1	0
4	0	1	0	1

 

4	6	0	0	3
0	0	6	3	1
0	4	0	1	0
4	0	1	0	1

ans = 1 (빠른 진행을 위해 한번에 적었다. 실제 코드에서는 하나씩 진행한다.)

4	6	0	0	3
0	0	7	3	2
0	6	0	4	0
5	0	4	0	3

bfs는 이렇게 진행된다.

void bfs(int _y, int _x) {
	int ans = 0;
	queue<pair<int, int>> q;
	vector<pair<int, int>> v;
	q.push({ _y, _x });

_y와 _x를 전달받고 int ans = 0을 선언한다.

그후 bfs에 사용할 queue와 0의 위치를 담을 vector를 선언한다.

그후 queue에 _y와 _x를 집어넣는다.

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		v.push_back({ y, x });

		visited[y][x] = true;
		ans++;

q가 비어있지 않은동안 반복문을 돌리며

y와 x를 q의 앞에서 뽑아낸후 q.pop을 한다.

그후 v에 y와 x를 집어넣고 visited[y][x]를 true로 바꾼뒤 ans에 1을 더한다.

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

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				if (map[ny][nx] == '0' && !visited[ny][nx]) {
					visited[ny][nx] = true;
					q.push({ ny, nx });
				}
			}
		}
	}

그후 현재 위치의 4방향을 돌아보며 map[i][j]가 0이고 방문하지 않았다면

visited[ny][nx]를 true로 바꾸고 q에 집어넣는다. 이걸 계속해서 반복하면 v에는 0의 위치들이 들어오게된다.

	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < 4; j++) {
			int ny = v[i].first + dy[j];
			int nx = v[i].second + dx[j];

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				if (map[ny][nx] != '0' && !visited[ny][nx]) {
					visited[ny][nx] = true;
					num[ny][nx] += ans;
					num[ny][nx] %= 10;
				}
			}
		}
	}

v를 하나씩 돌아보며 0주위에 벽인 부분이 있다면 num[ny][nx]에 ans를 더한다.

그후 visited를 true로 해준다.

1	1	0	0	1
0	0	1	1	1
0	1	0	1	0
1	0	1	0	1

위의 파란 0부분에서 주위에 있는 벽에 값을 더할때 자칫하면 빨간 부분의 벽에 값을 2번 더할수도있다.

그것을 방지하기 위해 방문을 확인한다.

	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < 4; j++) {
			int ny = v[i].first + dy[j];
			int nx = v[i].second + dx[j];

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				if (map[ny][nx] != '0') {
					visited[ny][nx] = false;
				}
			}
		}
	}

그후 하나씩 돌아보며 방문표시된 벽의 방문표시를 풀어준다.

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << num[i][j];
		}
		cout << '\n';
	}

마지막으로 num을 출력한다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
#include <vector>

using namespace std;

int n, m;
string map[1001];
int num[1001][1001];
bool visited[1001][1001];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { 1, 0, -1, 0 };

void bfs(int _y, int _x) {
	int ans = 0;
	queue<pair<int, int>> q;
	vector<pair<int, int>> v;
	q.push({ _y, _x });
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		v.push_back({ y, x });

		visited[y][x] = true;
		ans++;

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

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				if (map[ny][nx] == '0' && !visited[ny][nx]) {
					visited[ny][nx] = true;
					q.push({ ny, nx });
				}
			}
		}
	}
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < 4; j++) {
			int ny = v[i].first + dy[j];
			int nx = v[i].second + dx[j];

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				if (map[ny][nx] != '0' && !visited[ny][nx]) {
					visited[ny][nx] = true;
					num[ny][nx] += ans;
					num[ny][nx] %= 10;
				}
			}
		}
	}
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < 4; j++) {
			int ny = v[i].first + dy[j];
			int nx = v[i].second + dx[j];

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				if (map[ny][nx] != '0') {
					visited[ny][nx] = false;
				}
			}
		}
	}
}

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

	cin >> n >> m;
	memset(num, 0, sizeof(num));
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++) {
		cin >> map[i];
		for (int j = 0; j < m; j++) {
			if (map[i][j] != '0') num[i][j] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == '0' && !visited[i][j]) {
				bfs(i, j);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << num[i][j];
		}
		cout << '\n';
	}
}

전체코드다.