[백준] 16954 움직이는 미로 탈출

백준 16954 움직이는 미로 탈출 풀이입니다.

움직이는 미로 탈출

문제를 딱 읽자마자 bfs로 풀어야 겠다고 생각했다. 대신 좀 다른 점은 대각선으로 이동할 수 있다는 점과 가능 여부만 판단하면 되는 것이다. 따라서 방문 여부를 따지는 visit함수는 필요없었다.

처음엔 쉽다고 생각하고 풀다보니 함수를 빠져나올 조건이 갑자기 생각이 나지 않아서 30분간 멍때렸다.. 아직 갈길이 멀다…

코드는 다음과 같습니다.

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

char map[8][8];
char tmp[8][8];

int dx[9] = {-1,-1,-1,0,1,1,1,0,0}; // 왼위 위 오위 오 오아 아 왼아 왼 가운데
int dy[9] = {-1,0,1,1,1,0,-1,-1,0};
int high = 0;

void move_map() { // 위에서부터 아래로 밀리게끔 해주는 함수 
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 7; j++) {
			tmp[j + 1][i] = map[j][i];
		}
		tmp[0][i] = '.';
	}

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			map[i][j] = tmp[i][j];
		}
	}
}

bool solve() {
	queue<pair<int, int>> q;
	q.push({ 7,0 }); // x y

	while (!q.empty()) {
		int Size = q.size();
		while (Size--) { // 이동할수있는 모든 상황을 다 생각해야 하기 때문에 이 부분을 제거한다면 모든 경우의 수가 따져지지 않기 때문에 값이 틀리게 나올 수 있다. 
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			
			if (map[x][y] == '#') continue;
			if (x <= high) return true; // 가장 높이 있던 벽 이상으로 이동했을 경우 언젠간 도착할 수 있기 때문
			if (x == 0 && y == 7)return true;

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

				if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
				if (map[nx][ny] == '#') continue;
				q.push({ nx,ny });
			}
		}
		move_map();
		high++;
	}


	return false;
}

int main() {

	bool chk = true;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> map[i][j];
			if (map[i][j] == '#' && chk) { // 가장 높은 위치에 있는 벽을 확인하기 위해서 (high가 나을수록 높이 있다.)
				high = i;
				chk = false;
			}
		}
	}

	cout << solve();
	

	return 0;
}

• bfs를 좀 더 공부해야겠다.
• 조건 좀 꼼꼼히 잘 보자

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이