boj, 백준)16946. 벽 부수고 이동하기 4 ( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/16946

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

2. 문제 개요

N x M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

 

각각의 벽에 대해서 다음을 구해보려고 하는데,

 - 벽을 부수고 이동할 수 있는 곳으로 변경 한다.

 - 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

 

 

3. 문제 힌트

BFS를 사용하는 문제, 처음으로, 벽이 없는 곳의 넓이를 미리 세어보자.

 

그리고 벽이 있는 곳을 기준으로 생각해보면...

 

이렇게 미리 세어두고 어딘가에 저장하지 않고 모든 1에 대해서, ( 1이 최대 M x N개 있을 수 있으니, O(NM))

BFS를 실행한다면 O(NM)이기 때문에 시간복잡도는 O(N^2 M^2)가 될 것이다.

4. 문제 풀이

(3)번에서 말한 것처럼, 시간복잡도가 매우 커지기 때문에, 모든 1에 대해서 BFS를 하지 않도록 할 것이다. 그래서 미리 세어보는 것.

 

빈칸들을 모두 BFS로 연결하고 그룹을 매기고 몇 개가 있는지 미리 구해놓는다.

 

그러면, 다시 맵을 전체 순회할 때, 벽이 존재하는, 즉 값이 1인 곳에서 상하좌우를 살펴보는데, 상하좌우 중 벽이 아닌 곳의 값을 모두 더하면 된다.

 

예를 들어, 

000

010

000

이 입력으로 들어오면, 0인 칸에 대해서 넓이를 구할 때

 

999

919

999

이런 식으로 값을 미리 채워놓는 것이다.

 

이렇게 1을 기준으로 상하좌우 모두 1이 아닌 곳을 더하면 27이 되어버린다. 실제로는 9가 정답.

 

그래서 그룹번호를 매겨서 같은 그룹인지 체크하고, 9를 한 번만 더할 수 있도록 하는 것이다.

(예)

001

010

101

이 입력으로 오면

33x

3x1

x1x

과 같이 값이 미리 채워질 거고, 한가운데 1을 기준으로 생각해보면 3이 두 번 더해지기 때문에 그룹핑을 해야 한다.

오른쪽 위 1을 생각해보면 3+1로 4, 올바른 값을 나타낸다. 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

struct COORD {
	int y, x;
};

char map[1000][1000];
bool visited[1000][1000];

int ans[1000][1000];

int group[1000][1000];
int area[1000000];	//area[groupnum];

int n, m, num = -1;

const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

int main()
{
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; ++i)
		scanf("%s", map[i]);

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j) {
			if (map[i][j] == '0' && !visited[i][j]){
				++num;
				queue<COORD> q;

				q.push({ i,j });
				visited[i][j] = true;

				int cnt = 1;

				while (!q.empty()){
					COORD cur = q.front(); q.pop();
					group[cur.y][cur.x] = num;

					for (int dir = 0; dir < 4; ++dir) {
						COORD next;
						next.y = cur.y + dy[dir];
						next.x = cur.x + dx[dir];

						if (next.y < 0 || next.x < 0 || next.y >= n || next.x >= m || visited[next.y][next.x])
							continue;
						if (map[next.y][next.x] == '1')
							continue;

						q.push(next);
						visited[next.y][next.x] = true;
						++cnt;
					}
				}
				area[num] = cnt;
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {

			if (map[i][j] == '1') {
				int sum = 1;
				set<int> s;

				for (int dir = 0; dir < 4; ++dir) {

					COORD next;
					next.y = i + dy[dir];
					next.x = j + dx[dir];

					if (next.y < 0 || next.x < 0 || next.y >= n || next.x >= m || map[next.y][next.x]== '1')
						continue;

					if (s.find(group[next.y][next.x]) == s.end()) {
						sum += area[group[next.y][next.x]];
						s.insert(group[next.y][next.x]);
					}
						
				}
				ans[i][j] = sum;
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {

			if (map[i][j] == '1')
				printf("%d", ans[i][j] % 10);
			else
				printf("0");
		}
		printf("\n");
	}

	return 0;
}

6. 결과