백준 16946 c++ "벽 부수고 이동하기4" -[PlusUltraCode]

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

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

 

[필자 사고]

 

벽 부수고 이동하기 1,2,3,4 중 시리즈 문제이다.

 

대부분의 벽 부수고 문제는 벽을 부순다음 BFS탐색을 시작해야 됬다.

 

이 문제 또한 이전과 같은 방식을 사용하게 되면 시간이 초과된다.

 

따라서 필자는 0으로 되어있는 칸을 미리 전처리 탐색을 해줘서 이동할 수 있는 칸의 값을 부여해 줬다.

 

그 다음 마지막에 1인 불록 상,하,좌,우만 검사하여 각각 더해줬다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int N, M;
vector<vector<int>> Arr;
vector <vector<pair<int, int>>> Tank; //왼쪽은 분류 오른쪽은 카운트 
vector<vector<bool>> visited;

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void Input() {
	cin >> N >> M;
	Arr.resize(N);
	Tank.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(M);
		Tank[i].resize(M);
		visited[i].resize(M, false);
	}
	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			Arr[i][k] = str[k] - '0';
			Tank[i][k].first = Arr[i][k];
			Tank[i][k].second = 0;
		}
	}
	
}

void BFS(int sero, int garo,int Label) {
	if (Arr[sero][garo] == 1) {
		visited[sero][garo] = true;
		return;
	}
	queue<pair<int, int>> myQueue;
	myQueue.push({ sero,garo });
	visited[sero][garo] = true;
	vector<pair<int, int>> IndexTemp;
	IndexTemp.push_back({ sero, garo });
	int count = 1;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) == false)continue;
			if (visited[nextSero][nextGaro] == false
				&& Arr[nextSero][nextGaro] == 0) {
				visited[nextSero][nextGaro] = true;
				myQueue.push({ nextSero,nextGaro });
				count++;
				IndexTemp.push_back({ nextSero,nextGaro });
			}
		}
	}

	for (int i = 0; i < IndexTemp.size(); i++) {
		int sero = IndexTemp[i].first;
		int garo = IndexTemp[i].second;
		Tank[sero][garo].first = Label;
		Tank[sero][garo].second = count;
	}
}//라벨은 2부터시작함

void MakeDistinctAndCount() {
	int Label = 2;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (visited[i][k] == false) {
				BFS(i, k,Label);
				if (Arr[i][k] == 0) {
					Label++;
				}
			}
		}
	}


}//분류하고 카운트

void Solve() {
	vector<vector<int>> Arr2;
	Arr2 = Arr;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k] == 1) {
				vector<int> temp;
				int sum = 1;
				for (int j = 0; j < 4; j++) {
					int nextSero = i + dy[j];
					int nextGaro = k + dx[j];
					if (Inside(nextSero, nextGaro) == false)continue;
					if (Arr[nextSero][nextGaro] == 0) {
						auto it = find(temp.begin(), temp.end(), Tank[nextSero][nextGaro].first);
						if (it == temp.end()) {
							temp.push_back(Tank[nextSero][nextGaro].first);
							sum += Tank[nextSero][nextGaro].second;
						}
					}
				}
				
				Arr2[i][k] = sum;
			}
			
		}
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k] == 1) {
				cout << Arr2[i][k]%10;
			}
			else {
				cout << 0;
			}
		}
		cout << '\n';
	}


}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	MakeDistinctAndCount();
	Solve();

	
}