백준 16954 c++ "움직이는 미로 탈출" -[PlusUltraCode]

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
int dy[8] = { 0,1,1,1,0,-1,-1, - 1 };
typedef pair<int, int> Node;
int N = 8;
int Wall = 0;
vector<vector<int>> Arr;
vector<vector<int>> GameVec;
void Print() {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cout << GameVec[i][k] << " ";
		}
		cout << '\n';
	}
}
void Input() {
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			char ch;
			cin >> ch;
			if (ch == '.') {
				Arr[i][k] = 0;
			}
			else {
				Arr[i][k] = 1;
				Wall++;
			}
		}
	}
	GameVec = Arr;
	
}

void MovingWall() {
	vector<vector<int>> moving;
	moving = GameVec;
	moving[0] = { 0,0,0,0,0,0,0,0 };
	for (int i = 0; i < N - 1; i++) {
		
		moving[i + 1] = GameVec[i];
	}
	int wallCount = 0;
	for (int k = 0; k < N; k++) {
		if (GameVec[7][k] == 1) {
			wallCount++;
		}
	}
	Wall -= wallCount;
	GameVec = moving;
}

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

void BFS() {
	queue<Node> myQueue;
	myQueue.push({ 7,0 });
	int nowSize = myQueue.size();
	int countUp = 0;
	vector<Node> nextTank;
	
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
	
		nextTank.push_back({ nowSero,nowGaro });
		for (int i = 0; i < 8; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			
			if (Inside(nextSero, nextGaro) == false)continue;
			//이동
				//벽이 아니어야 됨
			//서있기
			if (GameVec[nextSero][nextGaro] == 0) {
			
				nextTank.push_back({ nextSero,nextGaro });
			 }
			
		}
		countUp++;
		if (nowSize == countUp) {
			MovingWall();
			
			
			for (int i = 0; i < nextTank.size(); i++) {
				int sero = nextTank[i].first;
				int garo = nextTank[i].second;
				if (GameVec[sero][garo] == 1)continue;
				else {
				
					myQueue.push({ sero,garo });
				}
			}
			if (myQueue.empty() == true) {
				cout << 0;
				return;
			}
			else {
				if (Wall == 0) {
					cout << 1;
					return;
				}
			}
			nowSize = myQueue.size();
			countUp = 0;
			nextTank.clear();
		}
	}
}



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

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

16954번: 움직이는 미로 탈출

 

[필자 사고]

 

 BFS 탐색 및 구현문제다.

 

필자는 벽을 1로 빈공간을 0으로 표시했다.

 

이 문제의 특이한점은 visted방문 배열을 사용하지 않았다는 점이다.

 

따로 벡터를 만들어 사람이 이동할수 있는 모든 경로를 저장해 놓고 벽이 내려오는 알고리즘 적용 뒤

 

벽과 사람이 만났으면 그  index를 큐에 넣지 않고 버리는 형식으로 문제를 풀어나갔다.

 

만약 모든 벽이 사라지면 유저는 원하는 목적지까지 도착 가능하니 바로 출력해주면 되겠다.

 

 

[소스 코드]