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

문제 설명

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 인접한 칸으로 이동하면 벽이 한칸씩 내려오는 상황에서 좌하단(7,0)에서 우상단(0,7)까지 이동할 수 있는지 여부를 확인하는 문제이다.

이때, 벽이 있는 칸은 이동할 수 없으며 이동한 직후 벽이 한 칸 내려온다.

만약 벽이 내려와 플레이어가 있는 칸에 도달하면 더 이상 움직일 수 없다.

 

이 문제를 풀기 위해서는 실제로 움직이고 벽을 내려보면 된다.

하지만, 배열을 하나씩 모두 내리는 작업은 번거로운 작업이다.

depth를 이용하여 벽이 몇 칸 내려왔다고 가정할 수 있다.

예를 들어, 플레이어가 3칸 움지였다면 벽이 3칸 아래로 내려왔을 것이다.

 

즉, depth를 통해 벽이 내려왔다 가정하고 움직일 칸에 벽이 있거나 그 위칸에 벽이 있다면 해당 분기는 절대 목적지로 갈 수 없다.

위칸을 확인하는 이유는 플레이어가 움직인 뒤, 바로 벽이 한 칸 내려오기 때문이다.

######..
.#.#.###
........
........
........
........
........
........

3번 움직인 상태에서 다음에 움직일 자리를 정하는 과정이다.

벽(#)이 실제로 내려온 게 아니라 3번 내려왔다고 가정한 것이다.

Maze[newY- depth][newX]

제일 왼쪽에 있는 초록색을 보면 위칸이 벽이라 이동할 수 없다.

다른 칸들도 마찬가지이다.

따라서 위의 경우는 정답이 0이다.

 

이러한 방식으로 DFS를 진행하면 정답을 구할 수 있다.

주의할 점은 배열의 범위를 넘어가는지 확인을 잘해야 한다.

이동하려는 칸이 범위밖인지, 이동하려는 칸의 윗칸이 범위밖인지 두 경우 모두 체크해야 한다.

 

만약 두 경우 중 하나라도 속한다면 해당 분기는 목적지로 갈 수 있는 경우이다.

이동하려는 칸이 범위의 밖인 경우는 제일 윗칸에 있던 벽을 넘었다는 뜻이다.

즉, 위로는 벽이 없다는 뜻이다.

해당 경우는 모든 벽이 내려가길 기다린 후 오른쪽으로만 이동하면 무조건 도달할 수 있다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N;
pair<int, int> Goal(0, 7);

vector<int> dy = { -1, -1, -1, 0, 0, 0, 1, 1, 1 };
vector<int> dx = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };

bool DFS(vector<vector<char>>& Maze, int depth, pair<int, int> Player)
{
    if (Player.first == Goal.first && Player.second == Goal.second)
    {
        return true;
    }

    bool bResult = false;
    for (int i = 0; i < 9; i++)
    {
        int newY = Player.first + dy[i];
        int newX = Player.second + dx[i];

        if (newY < 0 || newY >= N || newX < 0 || newX >= N) continue;
        if (newY - depth < 0) return true;
        if (Maze[newY- depth][newX] == '#') continue;
        if (newY - (depth + 1) < 0) return true;
        if (Maze[newY - (depth + 1)][newX] == '#') continue;

        bResult = (bResult || DFS(Maze, depth + 1, { newY,newX }));
    }

    return bResult;
}

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

    N = 8;

    vector<vector<char>> Maze(N, vector<char>(N));
    pair<int, int> Player(7, 0);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> Maze[i][j];
        }
    }

    cout << DFS(Maze, 0, Player);

    return 0;
}

---