백준 16954번 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

 

 

 

 

<접근방법>

조금 특이한 bfs문제 입니다.

벽이 있는 곳으로 이동할 수 없고, 벽이 없는 곳으로 이동했다고 하더라도

내가 이동한 후에 벽이 이동하므로 벽이랑 충돌하면 탈락입니다.

 

저는 나 이동 -> 벽 이동 -> 충돌시 고려안함 -> ... 반복하는 구조로 구현하였습니다.

이때, 벽 이동 구현에 유의해야합니다.

벽이 위아래로 붙어있을 경우가 있기 때문에, '동시에' 움직이는 구현을 해야합니다.

 

3차원 배열에다가 미리 시간별로 벽의 위치를 구현한 후에 시간을 조작하며 하는 방법도 있습니다.

이 방법이 구현이 조금 더 간단한 것 같습니다.

 

 

 

---

 

 

 

<코드>

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

struct point {
	int y, x;
};

int n, high;
char map[10][10];
int dy[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int dx[9] = { 0, 1, 1, 0, -1, -1, -1, 0, 1};
vector<point> wall;
queue<point> q;

void move_wall() {
	for (int i = 0; i < wall.size(); i++) {
		if (wall[i].y >= 8) continue;

		map[wall[i].y][wall[i].x] = '.';
		wall[i].y++;
	}
	for (int i = 0; i < wall.size(); i++) {
		if (wall[i].y >= 8) continue;

		map[wall[i].y][wall[i].x] = '#';
	}

	high++;
}

int bfs() {
	int cnt = 0;
	q.push({7, 0});

	while (!q.empty()) {
		int sz = q.size();
		for (int z = 0; z < sz; z++) {
			point t = q.front();
			q.pop();

			if (map[t.y][t.x] == '#') continue;
			if (t.y <= high) return 1;
			if (t.y == 0) return 1;

			for (int i = 0; i < 9; i++) {
				int ny = t.y + dy[i];
				int nx = t.x + dx[i];

				if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
				if (map[ny][nx] == '#') continue;

				q.push({ny, nx});
			}
		}
		move_wall();
	}
	return 0;
}

int main() {
	n = 8;
	bool flag = true;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> map[i][j];
			if (map[i][j] == '#') {
				wall.push_back({i, j});
				if (flag) {
					high = i;
					flag = false;
				}
			}
		}
	}
	
	cout << bfs() << '\n';
	return 0;
}

 

 

---

 

 

<느낀 점>

-이동 구현할 때는 항상 조심하자