<Baekjoon> #16946 BFS_벽 부수고 이동하기 4 c++

#16946 벽 부수고 이동하기 4
참고1

이때까지 많이 풀어보았던 BFS 문제들 처럼 똑같이 BFS 함수를 구현하고 현재 위치가 WALL=1 이면 BFS탐색을 통해 갈 수 있는 PATH=0의 개수를 count하고 리턴하여 그 수를 원래 WALL=1이 있던 자리에 넣어주고 이 과정을 WALL이 나올 때마다 반복해서 했다.

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
const int MAX = 1001;
const int WALL = 1;
const int PATH = 0;
int N, M;
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
vector<vector<int>> map;
bool discovered[MAX][MAX];

int bfs(int y, int x) {
	int cnt = 1;
	queue<pair<int, int>>q;
	q.push(make_pair(y,x));

	while (!q.empty()) {
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				int nx_y = cur_y + dy[i];
				int nx_x = cur_x + dx[i];

				if (nx_y < 0 || nx_x < 0 || nx_y >= N || nx_x >= M) continue;
				if (map[nx_y][nx_x] == PATH && !discovered[nx_y][nx_x]) {
					discovered[nx_y][nx_x] = true;
					q.push(make_pair(nx_y, nx_x));
					cnt++;
				}
			}
		}
	}
	return cnt;
}
int main() {
	memset(discovered, false, sizeof(discovered));
	cin >> N >> M;
	map = vector<vector<int>>(N, vector<int > (M));
	for (int i = 0; i < N; i++) {
		string tmp;
		cin >> tmp;
		for (int j = 0; j < M; j++) {
			int tmp2 = tmp[j] - '0';
			map[i][j] = tmp2;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == WALL) {
				int ans = bfs(i, j);
				ans %= 10;
				map[i][j] = ans;
				memset(discovered, false, sizeof(discovered));
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			printf("%d", map[i][j]);
		printf("\n");
	}
	return 0;
}

그런데 시간 초과가 나고 다른 포스팅을 참고 하여 다른 풀이로 풀었다.

접근 방법을 다르게 하여, 일단 PATH Blob의 개수를 count하여 저장하고,WALL이 나왔을 때 그 WALL과 상,하,좌,우로 인접한 곳에 PATH Blob이 있다면 그 수를 더해준다.

1. PathBlob 채우기
   맵의 전체 부분을 탐색 하다가 PATH=0을 만나면 dfs 함수를 호출하여 해당 PATH과 인접한 모든 PATH를 count하여 그 크기를 PathBlob에 저장한다.
   
   위 예시에서
   int pathBlobSize=6 이고

   blobNum[0][2]=blobNum[0][3]=0,
   blobNum[1][0]=blobNum[1][1]=blobNum[2][0]=1,
   blobNum[2][2]=2,
   blobNum[2][4]=3,
   blobNum[3][1]=4,
   blobNum[3][3]=5 이 저장된다.

2.벽과 상,하,좌,우로 인접한 PathBlob을 찾아 더해준다

answer[i][j] += pathBlob[blobNum[nx_y][nx_x]];
//nx_y, nx_x 는 현재 위치 (i,j)를 기준으로 상,하,좌,우의 좌표

여기서 문제점이 생기게 되는데 왼쪽과 위쪽에 인접한 pathBlob은 같은 blob이기 때문에 한 번만 더해주어야 한다.

그래서 한 번 pathBlob을 방문하면 이미 방문했다는 표시로
set<int> Search를 이용한다.
WALL과 인접한 PATH를 찾아 이 pathBlob의 크기를 더해줄 때 몇 번 째 pathBlob인지 즉 blobNum을 Search에 넣어준다.

Search.insert(blobNum[nx_y][nx_x]);
answer[i][j] += pathBlob[blobNum[nx_y][nx_x]];

그리고 다음에 다시WALL과 인접한 PATH를 찾았을 때 이 PATH가 이미 더해준 PATH인지를 탐색하기 위해

if (Search.find(blobNum[nx_y][nx_x]) == Search.end())

다음과 같이 Search에 현재 더하려고 하는 blobNum이 있는지 보고 없으면 크기를 더해준다
(set.find()연산에서 찾는 값이 없으면 set.end()를 return한다)

전체 코드 (변수가 많아 헷갈리지만 차근 차근 본다)

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

using namespace std;

const int WALL = 1;
const int PATH = 0;
const int MAX = 1001;
int N, M;
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

vector<int> pathBlob;
vector<vector<int>> map;

int blobNum[MAX][MAX];
int discovered[MAX][MAX];
int answer[MAX][MAX];
int pathBlobSize = 0;

void dfs(int y, int x) {
	discovered[y][x] = true;
	blobNum[y][x] = pathBlobSize;
	int cnt = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));

	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 nx_y = cur_y + dy[i];
			int nx_x = cur_x + dx[i];

			if (nx_y < 0 || nx_x < 0 || nx_y >= N || nx_x >= M) continue;
			if (map[nx_y][nx_x] == PATH && !discovered[nx_y][nx_x]) {
				q.push(make_pair(nx_y, nx_x));
				discovered[nx_y][nx_x] = true;
				blobNum[nx_y][nx_x] = pathBlobSize;
				cnt++;
			}
		}
	}
	pathBlob.push_back(cnt);
}
void soultion() {
	memset(answer, 0, sizeof(answer));
	memset(blobNum, -1, sizeof(blobNum));
	memset(discovered, false, sizeof(discovered));
	cin >> N >> M;
	map = vector<vector<int>>(N, vector<int >(M));

	//input data to map
	for (int i = 0; i < N; i++) {
		string tmp;
		cin >> tmp;
		for (int j = 0; j < M; j++) {
			int num = tmp[j] - '0';
			map[i][j] = num;
		}
	}

	//find PATH area 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == PATH && !discovered[i][j]) {
				dfs(i, j);
				pathBlobSize++;
			}
		}
	}

	//find WALL and Add neighbour PATH area
	for (int i = 0; i < N; i++) {
		for (int j=0; j < M; j++) {
			if (map[i][j] == WALL) {
				set<int> Search;
				for (int k = 0; k < 4; k++) {
					int nx_y = i + dy[k];
					int nx_x = j + dx[k];

					if (nx_y < 0 || nx_x < 0 || nx_y >= N || nx_x >= M) continue;
					if (map[nx_y][nx_x] == PATH) {
						if (Search.find(blobNum[nx_y][nx_x]) == Search.end()) {
							Search.insert(blobNum[nx_y][nx_x]);
							answer[i][j] += pathBlob[blobNum[nx_y][nx_x]];
						}
					}
				}
				answer[i][j] += 1;
				answer[i][j] %= 10;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d", answer[i][j]);
		}
		printf("\n");
	}
}

int main() {
	soultion();
	return 0;
}