16954. 움직이는 미로 탈출

이 문제의 경우, 추천하지 않습니다. 

이 문제는 기본의 완전탐색에 조건이 하나가 추가된 문제입니다. 완전탐색문제의 경우, 구현을 연습하는 문제입니다. 하지만, 이 문제의 추가된 조건은 구현시 실력향상에 도움이 되기 어려우며, 조건을 구현하는 방법이 단일적이기 때문입니다. 또한, 문제도 애매모호하며, 다수의 문제에 대한 의문점을 가질 수 있는 문제이기 때문입니다. 

완전탐색을 연습하고자 이 문제를 풀는 사람들은 이 문제말고 다른 정석적인 완전탐색문제를 풀어보길 권장합니다. 아래에 제가 정리한 정석적인 완전탐색문제의 링크가 있는 페이지를 첨부합니다. 도움이 되셨으면 좋겠습니다. 

https://hyemsinabro.tistory.com/122

알고리즘 기초 문제 모음 vol.1

 

 

 

이 문제의 경우, 문제대로 구현하면 해결되는 문제이다.

하지만, 문제의 설명이 너무 어렵게 되어있어 해설이 필요하다. 

문제요약 )

1. 캐릭터는 8방(위/아래/오른쪽/왼쪽/오른쪽위대각선/왼쪽위대각선/오른쪽아래대각선/왼쪽아래대각선)과 함께 제자리도 가능하다. 
2. 벽이 1초마다 한칸이 내려간다고 한다.

문제 요약은 2개로 축소할 만큼 간단하다. 문제요약 1 을 읽어보면, 이 문제가 완전탐색이라는 것을 알 수 있다. 

문제요약 2에서 단순한 완전탐색이 아니라는 것을 알 수 있다. 그러면 이 문제의 해결책은 완전탐색을 기본으로 하고 문제요약 2만 해결을 해주면 해결이 가능한 문제이다. 

문제요약 2에 대한 나의 해결방안은 

 => 캐릭터의 행위치를 초가 지날때마다 -1씩해주는 것이다. 단 이것은 맨 위에 벽이 없는 행이 하나 필요하다. 

벽이 내려간다는 것은 캐릭터가 한칸 올라간다는 말과 동일하다. 왜 이렇게 구현하였냐면 map 즉, 벽을 직접 이동시킨다면, 매 초가 지날때마다 map 배열의 전체를 이동시켜주는 연산이 필요하다. 연산에도 많은 시간이 들지만, 구현도 귀찮다. 벽이 다 없어졌는지 판단하고 다 없어지면, 이동연산을 중단하여 벽이없는 map에서 캐릭터를 움직어야되기 때문이다. 

 

아래는 이러한 방법으로 구현한 코드이다.

#include <iostream>
using namespace std;

int dx[] = {0, 0,-1,0,1,1,1,-1,-1 };
int dy[] = {0, -1,0,1,0,-1,1,-1,1 };
char map[10][10] = { 0 };
int search(int i, int j) {
	if ((i == 1||i==0) && j == 8) {
		return 1;
	}
	i -= 1;
	if (i < 0)
		i = 0;
	if (map[i][j] == '.') {
		map[i][j] = 0;
		for (int k = 0; k < 9; k++) {
			if (i + dx[k] >= 0 && i + dx[k] <= 8 && j + dy[k] >= 1 && j + dy[k] <= 8) {
				if (map[i + dx[k]][j + dy[k]] == '.'|| map[i + dx[k]][j + dy[k]] == 0) {
					if (search(i + dx[k], j + dy[k])) {
						return 1;
					}
				}
			}
		}
		map[i][j] = '.';
	}
	return 0;
}

int main(void) {

	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	int x = 8;
	int y = 1;
	for (int i = 1; i <= 8; i++) {
		map[0][i] = '.';
	}
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			cin >> map[i][j];
		}
	}

	cout<<search(x+1, y);
	return 0;
}

 

 

 

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

16954번: 움직이는 미로 탈출