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

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

16954번: 움직이는 미로 탈출

BFS를 이용한 문제였습니다!

문제 조건

출력 예시

 

3차원 배열을 만든뒤, 0~8초까지의 벽의 움직임을 담고, 9방향 탐색을 하면 되는 문제였습니다.

 

문제 접근 방법

1. 벽의 위치를 vector를 이용해 저장합니다.

2. 벽의 갯수가 0개라면 1출력, 아니면 탐색을 시작합니다.

3. 0~8초까지 저장한 벽의 위치를 이용해 N초가 지났을때의 벽의 위치를 저장합니다.

4. 9방향 탐색을 통해서 탈출할 수 있으면 1, 아니면 0을 return한 뒤, 출력합니다.

 

문제 접근 방법 - 3번

void make_map() {
	for (int t = 0; t <= 8; t++) {
		for (int i = 0; i < wall.size(); i++) {
			if (wall[i].first + t <= 8) down_map[t][wall[i].first + t][wall[i].second] = '#';
		}
	}
	for (int t = 0; t <= 8; t++) {
		for (int i = 1; i <= 8; i++) {
			for (int j = 1; j <= 8; j++) {
				if (down_map[t][i][j] == '#') continue;
				down_map[t][i][j] = '.';
			}
		}
	}
}

1초마다 아래로 한칸씩 내려오기 때문에 t초에는 "wall[i].first+t"칸에 위치하게 됩니다. 

해당 칸이 8보다 작을 때는 내려주면 되고, 8보다 크다면 소멸하기에 저장을 안하면 됩니다.

 

문제 접근 방법 - 4번

int bfs() {
	queue<qu> q;
	q.push({8,1,0});
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int t = q.front().t;
		q.pop();
		if (x == 1) {
			return 1;
		}
		if (find_wall(x, t)) {
			return 1;
		}
		for (int i = 0; i < 9; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= 8 && yy <= 8) {
				if (down_map[t][xx][yy] == '.' && down_map[t + 1][xx][yy] == '.') {
					q.push({ xx,yy,t + 1 });
				}
			}
		}
	}
	return 0;
}

움직이는 방향이 9가지입니다. (상하좌우, 대각선 4방향, 현재위치) 

도착점에 도착할 수 있는 경우는 2가지입니다.

1. 맨 윗줄에 도착했을 경우 -> 벽이 전부 없는 상태임으로 도착할 수 있다.

2. 현재 X의 위치에서 1 ~ X-1 칸에 벽이 없는 경우

위 2가지 경우 일때는 1을 return 하면 됩니다.

check를 통해서 온 지점을 확인하지 않아도 됩니다. -> t초에 따라서 칸이 계속 바뀌기 때문에 이전에 도착했던 곳을 방문 하지 않음(ex) 1초, (8,7) -> 2초, (8,7))

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

char map[9][9];
char down_map[9][9][9];
int dx[9] = { 0,1,0,-1,0,1,1,-1,-1 };
int dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
vector<pair<int, int>> wall;
typedef struct qu {
	int x;
	int y;
	int t;
}qu;

bool find_wall(int x, int t) {
	bool Find = true;
	for (int i = 1; i <= x - 1; i++) {
		for (int j = 1; j <= 8; j++) {
			if (down_map[t][i][j] == '#') Find = false;
		}
	}
	return Find;
}

int bfs() {
	queue<qu> q;
	q.push({8,1,0});
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int t = q.front().t;
		q.pop();
		if (x == 1) {
			return 1;
		}
		if (find_wall(x, t)) {
			return 1;
		}
		for (int i = 0; i < 9; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= 8 && yy <= 8) {
				if (down_map[t][xx][yy] == '.' && down_map[t + 1][xx][yy] == '.') {
					q.push({ xx,yy,t + 1 });
				}
			}
		}
	}
	return 0;
}

void make_map() {
	for (int t = 0; t <= 8; t++) {
		for (int i = 0; i < wall.size(); i++) {
			if (wall[i].first + t <= 8) down_map[t][wall[i].first + t][wall[i].second] = '#';
		}
	}
	for (int t = 0; t <= 8; t++) {
		for (int i = 1; i <= 8; i++) {
			for (int j = 1; j <= 8; j++) {
				if (down_map[t][i][j] == '#') continue;
				down_map[t][i][j] = '.';
			}
		}
	}
}

void solve() {
	make_map();
	int answer = bfs();
	cout << answer;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			cin >> map[i][j];
			if (map[i][j] == '#') {
				wall.push_back(make_pair(i, j));
			}
		}
	}
	if (wall.size() == 0) cout << "1";
	else {
		solve();
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!