[G3] 백준 16954번 움직이는 미로 탈출 C++ 백트래킹

리뷰

 

각 단계별 맵과 현재 위치를 고려하여 목표 위치까지 이동할 수 있는지를 구하는 문제

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

 

전역 변수

• lst : 초기 맵 정보를 저장할 문자열 벡터, 크기는 8로 설정한다.
• ans : 정답 정보를 저장할 정수형 변수
• v : 각 단계별 현재 위치에 대한 방문 정보를 저장할 3차원 정수형 배열, 8 * 8 * 8크기로 설정한다.
• dx, dy : 상하좌우, 대각선, 제자리를 고려한 방향배열
• Pos : 현재 위치를 나타낼 구조체

 

함수

1. moving

void moving(vector<string>& map)

 

1. 현재 맵에 존재하는 벽들을 모두 한칸씩 내려주는 시뮬레이션을 진행한다.
2. 맵의 아래서 부터 swap을 통해 각 행을 변경해 주고, 마지막에 0번행을 빈 칸으로 세팅해 준다.
3. level이 0이 아닐때, 즉 한번이라도 이동을 한 뒤에 실행시켜 준다.

2. bt

void bt(int level, vector<string>& map, Pos pos)

 

1. 백트래킹을 통해 현재 재귀 단계, 맵 상태, 위치를 매개변수로 받아 시뮬레이션을 진행한다.
2. 만약 ans가 1이 되었을 경우 더 이상 탐색할 필요가 없으니 바로 리턴해 주면 된다.
3. level이 8이 되었을 경우 모두 벽이 내려올때 까지 살아있는 상태이므로 ans를 1로 설정해 준다.
4. 매개변수로 받은 map정보를 new_map으로 깊은 복사를 해준 뒤 moving함수를 통해 맵을 움직여 준다.
5. 만약 움직이고 나서의 나의 위치가 벽에 닿았다면 더 이상 탐색하지 않고 리턴 해준다.
6. 방향 배열을 모두 탐색해 주고 다음 위치가 범위 안이고, 미방문이고, 벽이 아니라면 이동을 진행한다.
7. 이동 후에는 방문 처리를 해주고 재귀 단계 증가, 새로운 맵, 새로운 좌표로 재귀를 이어나가면 된다.
8. 다음 위치가 맵의 오른쪽 위라면 ans를 1로 변경한다. 근데 아마 level이 8되는게 더 빠를듯 하다.

 

문제풀이

1. 문자열 벡터 lst에 8개의 문자열을 받아와 초기 맵 정보를 초기화 해준다.
2. 시작 위치 pos를 7, 0으로 설정하고 level = 0, 초기 맵 lst, 초기 위치 pos를 백트래킹의 매개변수로 전달한다.
3. 백트래킹을 통해 ans가 1이 되는지 여부를 체크해 준다.
4. 탐색이 종료된 후에 ans에 저장된 값을 출력해 주면 된다.

 

참고 사항

알고리즘 분류에 너비 우선 탐색이 기재되어 있는데 나는 백트래킹과 시뮬레이션을 통해 더 직관적인 문제 풀이가 가능했다.

시간도 0ms인걸 보면 가지치기도 자연스럽게 잘 되고 괴랄한 엣지케이스는 없는듯 하다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
vector<string> lst(8);

int ans;
int v[8][8][8];
int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1, 0 };
int dy[] = { 1, -1, 0, 0, 1, -1, 1, -1, 0 };

struct Pos {
	int x, y;
};

void moving(vector<string>& map) {
	for (int i = 6; i >= 0; i--) swap(map[i], map[i + 1]);
	map[0] = "........";
}

void bt(int level, vector<string>& map, Pos pos) {
	if (ans) return;
	if (level == 8) {
		ans = 1;
		return;
	}
	vector<string> new_map = map;
	if (level) moving(new_map);
	int cx = pos.x, cy = pos.y;
	if (new_map[cx][cy] == '#') return;
	for (int i = 0; i < 9; i++) {
		int nx = cx + dx[i], ny = cy + dy[i];
		if (0 <= nx && nx < 8 && 0 <= ny && ny < 8 && !v[level][nx][ny] && new_map[nx][ny] != '#') {
			v[level][nx][ny] = 1;
			if (nx == 0 && ny == 7) ans = 1;
			bt(level + 1, new_map, { nx, ny });
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 8; i++) cin >> lst[i];
	Pos pos = { 7, 0 };
	bt(0, lst, pos);
	cout << ans;
}