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

www.acmicpc.net/problem/16946

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

[풀이]

bfs를 사용하여 풀었다.

각 벽마다 주변에 있는 0의 개수를 세도록 하면 visited[1001][1001]배열을 매번 false로 초기화 해줘야 하기 때문에 시간 초과가 난다.

※방문하지 않은 0마다 bfs를 호출하여 연결된 0의 개수를 센 다음, 탐색하면서 만난 벽들에 그 개수를 더해주도록 하였다.

 

#include <iostream>
#include <queue>
#include <cstdio>//scanf
#include <cstring>//memset
using namespace std;

struct Pos {
	int x, y;
};

int N, M;
int Map[1001][1001];
bool visited[1001][1001];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void bfs(int startx, int starty) {
	queue<Pos>q;
	vector<Pos>wall;
	q.push({ startx,starty });
	visited[startx][starty] = true;
	int cnt = 1;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			if (Map[nx][ny] == 0 && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				q.push({ nx,ny });
				cnt++;
			}
			//현재 탐색하는 공간에 인접한 벽 저장
			else if (Map[nx][ny] != 0 && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				wall.push_back({ nx,ny });
			}
		}
	}
	//탐색하면서 나왔던 벽들에 0의 개수 더해주기
	for (int i = 0; i < wall.size(); i++) {
		Map[wall[i].x][wall[i].y] += cnt;
		visited[wall[i].x][wall[i].y] = false;
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &Map[i][j]);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j] == 0 && visited[i][j] == false)
				bfs(i, j);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d", Map[i][j]%10);
		}
		printf("\n");
	}
	return 0;
}