백준 16926 - 벽 부수고 이동하기 4(C++)

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

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

문제 조건

출력 예시

N*M의 값이 주어졌을 때, (i , j) 칸의 벽을 부셨을 때, 해당 칸에서 이동할 수 있는 곳은 몇 칸인지를 물어보는 문제입니다.

예를 들어 아래와 같은 입력이 주어졌을때,

(1,1)의 벽을 허문 모습이다.

(1,1)의 벽을 허문뒤, 해당 칸에서 이동할 수 있는 곳의 갯수를 세는 것입니다. (1,1) 에서는 값이 4가 되겠습니다.

이와 같은 과정을 벽의 갯수 만큼 반복해주면 됩니다.

 

그렇다면 가장 쉬운 방법이 있습니다. N개의 벽을 하나씩 허문 다음, BFS를 돌려주면 되는 방법입니다.

즉 BFS를 N번 만큼 돌린다는 의미인데, 시간 제한이 2초이며, 최대 배열의 크기가 1000*1000 이니, 시간초과가 생길 수

밖에 없습니다.

 

그렇기에 다른 방법을 사용해야 하는데, 제가 사용한 방법은, group으로 묶어주는 것입니다.

즉, 벽을 허물기 전에, 하나의 빈방에서 갈 수 있는 곳의 최댓값을 구한뒤에, 하나의 그룹으로 묶은 뒤, 최댓값을 저장하는 방법입니다.

위의 배열을 다시 예시로 들어보자면

위와 같은 그룹으로 묶이며, 해당 그룹에서의 최댓값도 동시에 저장해줄 수 있습니다.

 

그럼 이제 벽을 부셨을 경우에 갈 수 있는 칸을 구하기가 쉬워집니다.

해당 벽에서 상하좌우 탐색을 통해서 붙어있는 그룹 번호를 저장한뒤, 해당 그룹의 값 만큼 더해주면 됩니다. 이때 그룹은 한번씩만 더해줘야 한다는 것을 주의해야합니다.

 

문제 접근 방법

1. 벽의 좌표를 저장한다.

2. 빈 공간이 있을 경우, 해당 칸에서 갈 수 있는 곳의 최댓값을 구하고, 칸들을 그룹으로 묶어준다.

3. 벽에서 4방향 탐색을 통해서 갈 수 있는 그룹을 확인하고 해당 그룹의 값을 한번씩만 더해준다.

 

 

자세한 것은 코드를 참고해주세요

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <string>

using namespace std;

int N, M;
int map[1001][1001];
int check[1001][1001];
int ans[1001][1001];
int dx[4] = { 1,0, -1,0 };
int dy[4] = { 0,1,0,-1 };
int number = 1;
vector<pair<int, int>> wall;
vector<int> group;

int bfs(int x1, int y1, int num) {
	queue<pair<int, int>> q;
	int cnt = 1;
	q.push(make_pair(x1, y1));
	check[x1][y1] = num;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
				if (check[xx][yy] == 0 && map[xx][yy] == 0) {
					check[xx][yy] = num;
					q.push(make_pair(xx, yy));
					cnt++;
				}
			}
		}
	}
	return cnt;
}

void solve() {
	group.push_back(0);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j] == 0 && check[i][j] == 0) {
				int cnt = bfs(i, j, number);
				group.push_back(cnt);
				number++;
			}
		}
	}
	for (int i = 0; i < wall.size(); i++) {
		int x = wall[i].first;
		int y = wall[i].second;
		ans[x][y] += 1;
		vector<int> add;
		for (int j = 0; j < 4; j++) {
			int xx = x + dx[j];
			int yy = y + dy[j];
			int now_add = check[xx][yy];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {		
				bool flag = true;
				for (int k = 0; k < add.size(); k++) {
					if (add[k] == now_add) {
						flag = false;
					}
				}
				if (flag) {
					add.push_back(now_add);
					ans[x][y] += group[now_add];
					ans[x][y] %= 10;
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << ans[i][j];
		}
		cout << "\n";
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%01d", &map[i][j]);
			if (map[i][j] == 1) {
				wall.push_back(make_pair(i, j));
			}
		}
	}
	solve();

	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!