[백준] 16954-움직이는 미로 탈출(C++)

문제링크: https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

 

bfs, 시뮬레이션 문제

 

 

접근방식

 

1. 욱제라는 사람의 이동은 bfs로 구현이 가능

2. 욱제이동과 벽이동을 번갈아가며 진행하면서 결과값을 도출하자

 

문제풀이 

 

1. bfs를 통해서 이동이 가능한 경로를 저장하며 진행

이때, 방문노드는 매턴마다 초기화하는데 그 이유는 다음턴에 다시 해당좌표로 이동할수도 있기 때문

........

........

........

........

........

.#######

#.......

........

ex) 위와 같은 예제에서 첨좌표로 되돌아 오는 것

 

2. 벽이동은 벽좌표들을 vector에 넣어 관리하며 진행 

 

 

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

typedef struct a {
	int y;
	int x;
}dir;

dir d[9] = { {0,0}, {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
string arr[8]; // 0base; 시작점은 7,0 도착점은 0,7 이다.
vector <dir> vec; // 벽을 저장할 벡터
queue <dir> que;

bool result = 0;
bool visited[8][8];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	for (int i = 0; i < 8; i++) {
		cin >> arr[i];
		for (int j = 0; j < 8; j++) {
			if (arr[i][j] == '#')
				vec.push_back({ i,j });
		}
	}
	que.push({ 7,0 });

	while (!que.empty()) { //큐가 비었으면 종료되는 구조 

		//1. 욱제의 이동
		int cnt = que.size();
		memset(visited, 0, sizeof(visited));

		while (cnt--) { // 갯수만큼

			int y = que.front().y;
			int x = que.front().x;
			que.pop();
			

			if (y == 0 && x == 7) {
				result = true;
				break;
			} 
			if (arr[y][x] == '#') //벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.
				continue;

			for (int i = 0; i < 9; i++) {
				int ny = y + d[i].y;
				int nx = x + d[i].x;
				if (ny < 0 || ny > 7 || nx < 0 || nx > 7 || arr[ny][nx] == '#') //방문여부는 체크하지 않는다 왔다 갔다 할수도 있자나 
					continue;
				if (visited[ny][nx] == 1)
					continue;
				visited[ny][nx] = 1;
				que.push({ ny,nx });
			}
		}

		//2. 벽이동
		
		for (int i = 0; i < 8; i++)
			arr[i] = "........";
		for (int i = 0; i < vec.size(); i++) {
			int y = vec[i].y;
			int x = vec[i].x;

			if (y == 7) {
				vec.erase(vec.begin() + i);
				i--;
			
				continue;
			}


			arr[y + 1][x] = '#';
			vec[i].y++;

		}

		if (result == true) //도달했으면 조기종료 
			break;
		
		/*
		cout << endl;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++)
				cout << visited[i][j];
			cout << endl;
		}
		cout << endl;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++)
				cout << arr[i][j];
			cout << endl;
		}
		cout << "quesize " << que.size() << endl;
		*/
	}


	cout << result << endl;
	return 0;
}