[G2] 백준 16946번 벽 부수고 이동하기 4 C++ BFS, FloodFill, 너비 우선 탐색

리뷰

 

일반적인 BFS를 사용하니 바로 시간 초과가 출력되었다!!

벽을 의미하는 1을 보기 보단, 0부터 본 후에 1을 체크하는 방식이 효율적인 문제였다.

 

위에서부터 차례대로 group정보를 배열, 벡터, unordered_map을 사용하여 관리한 정보이다.

배열이 시간은 가장 빠르고 벡터가 메모리 낭비가 덜 심하고 해시는 그닥 효율이 좋지 못했다.

따라서 해당 문제는 벡터를 활용한 방법으로 설명하겠다.

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

 

문제 풀이

전역변수

• lst : 맵을 저장할 문자열 벡터
• group : 그룹의 면적을 저장할 벡터, 인덱싱을 위해 크기를 1을 가진 상태로 시작한다.
• groups : 그룹의 면적을 2D맵에 나타내기 위한 배열
• v : 방문을 체크하기 위한 배열, 사실상 groups 배열하나로 관리가 가능하다.
• dx, dy : 4방향 탐색을 하기 위한 배열
• n, m : 행의 크기 n, 열의 크기 m
• Pos : 2차원 탐색을 위한 x, y 좌표를 나타내기 위한 구조체

1. n과 m값을 입력 받고 맵 크기를 n으로 맞추어 준 뒤 맵 정보를 문자열로 받아와 준다.
2. 그룹은 1부터 시작할 것이기 때문에 index를 1로 맞추어 주고 2차원 배열 탐색을 시작한다.
3. 만약 맵상에서 0을 만났고, 해당 좌표가 방문처리 되어있지 않다면 floodfill 함수를 실행해 주고 index를 증가시킨다.
4. floodfill 함수의 매개 변수는 탐색을 시작할 좌표 sx, sy와 현재 그룹을 묶을 key(index)이다.
5. 현재를 방문처리, groups에는 key를 기록해 주고 cnt는 1개로 설정해 준 뒤 큐에 좌표를 삽입한다.
6. 큐가 빌때까지 탐색을 진행하고 방문하지 않았고, 맵상 0인 모든 곳을 방문처리 및 groups에 key를 기록해 준다.
7. group벡터에 현재 그룹의 넓이 cnt를 push해준다. 이는 나중에 groups에서 인덱스로 파싱이 가능하게끔 하는 것이다.
8. 맵상에서 모든 0에 대해 그루핑이 끝났다면 이제 출력을 할 일만 남았다.
9. 맵상에서 0을 만났다면 0을 출력해 주고, 1을 만난 경우엔 chk 함수를 통해 탐색을 추가로 시작한다.
10. chk의 매개변수로는 탐색을 시작할 좌표이고 벽을 허문 상태기에 cnt를 1로 초기화 해준다.
11. 중복 제거를 위해 set를 사용해 준다. 오름 차순은 의미 없기에 unordered_set를 사용해 주면 된다. keys로 초기화
12. 4방향을 탐색하고 해당 위치가 범위 내면서 벽이 아니고 그룹이 존재한다면 keys에 해당 그룹을 추가해 준다.
13. keys에 저장된 값을 group의 인덱스로 매핑하여 cnt에 추가해 준뒤 cnt를 리턴해 준다.
14. 리턴 받은 값을 10으로 나눈 나머지를 출력해 주면 된다. 해당 로직을 n * m범위 모두 진행해 주면 된다.

 

참고 사항

set을 통해 중복을 제거해 주지 않으면 같은 그룹일지라도 중복하여 더하게 된다.

위에서도 언급했지만 방문 배열 대신 groups를 사용해도 된다, 대신 벽인 경우만 if문으로 잘 예외처리 해줘야 한다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<unordered_set>

using namespace std;

vector<string> lst;
vector<int> group(1);
int groups[1000][1000] = { 0, };
int v[1000][1000] = { 0, };
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int n, m;

struct Pos {
	int x, y;
};

int chk(int sx, int sy) {
	int cnt = 1;
	unordered_set<int> keys;
	for (int i = 0; i < 4; i++) {
		int nx = sx + dx[i], ny = sy + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != '1' && groups[nx][ny]) keys.insert(groups[nx][ny]);
	}
	for (int key : keys) cnt += group[key];
	return cnt;
}

void floodfill(int sx, int sy, int key) {
	queue<Pos> q;
	q.push({ sx, sy });
	int cnt = 1;
	v[sx][sy] = 1;
	groups[sx][sy] = key;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && lst[nx][ny] == '0') {
				v[nx][ny] = 1;
				groups[nx][ny] = key;
				cnt++;
				q.push({ nx , ny });
			}
		}
	}
	group.push_back(cnt);
}

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

	cin >> n >> m;
	lst.resize(n);
	for (int i = 0; i < n; i++) cin >> lst[i];

	int index = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == '0' && !v[i][j]) floodfill(i, j, index++);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == '0') cout << 0;
			else cout << chk(i, j) % 10;
		}
		cout << "\n";
	}
}