[BAEKJOON] 16946번 벽 부수고 이동하기 4

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

 

문제조건

1. N×M의 행렬로 표현되는 맵
2. 0 : 이동가능, 1 : 벽
3. 각각의 벽에대해 해당 벽을 부수고, 이동가능한 장소로 바꾼뒤 그 위치에서 이동가능한 칸의 개수

접근방법

 

처음에는 정말 단순하게 모든 벽에 대해서 BFS를 돌렸다가 시간초과가 났다.

최악의 경우 1000^3 이면 10억인데,, 대략 10초가량 소요되는 것이다.

그래서 어떻게 하면 시간을 줄여가며 해결할까 고민 한 결과,,, visited 배열을 각각 벽에대해 초기화 시켜주는 작업을 안해주면 시간제한에 안걸릴것이라고 생각했다. 그래서 벽을 탐색하는 것이아니라, 맵에서 이동가능한 부분인 0인 값에서 부터 BFS를 진행해서 인접한 벽에 누적으로 값을 더하고, visited배열을 초기화해줄 필요가 없는 것을 알았다.

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int map[1001][1001], visited[1001][1001];
int n, m;
int dy[] = { -1, 0 , 1, 0 };
int dx[] = { 0 , -1, 0 ,1 };

void bfs(int y, int x) {
	queue<pair<int, int> > q;
	vector<pair<int, int> > v;
	q.push({ y, x });
	visited[y][x] = 1;
	int cnt = 1;
	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if (map[ny][nx] == 0 && visited[ny][nx] == 0) {
				visited[ny][nx] = 1;
				q.push({ ny,nx });
				cnt++;
			}
			else if (map[ny][nx] != 0 && visited[ny][nx] == 0) {
				visited[ny][nx] = 1;
				v.push_back({ ny,nx });
			}
		}
	}
	for (int i = 0; i < v.size(); i++) {
		map[v[i].first][v[i].second] += cnt;
		visited[v[i].first][v[i].second] = 0;
	}

}

int main(){
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			map[i][j] = s[j] - '0';
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0 && !visited[i][j]) bfs(i, j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << map[i][j] % 10;
		}
		cout << "\n";
	}
}

visited배열을 초기화 하는 것이아닌, 벽에 해당하는 부분만 BFS를 돌때마다 마지막에 false로 바꾸어줘서 배열을 초기화하는 1000^2의 시간이 단축되었다. 뭔가 안풀릴때는 생각의 전환!!