[Algorithm]Baekjoon 16954번 :: 움직이는 미로 탈출

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

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
struct Wall
{
    int y;
    int x;
};
 
int dirs[9][2] = {
        {0,1},  {-1,0}, {-1,1},
        {0,-1}, {0,0}, {-1,-1},
        {1,-1}, {1,0}, {1,1} };
 
bool IsInRange(int y, int x)
{
    if (y == -1 || y == 8) return false;
    if (x == -1 || x == 8) return false;
 
    return true;
}
 
bool dp[8][8][1000] = { false };
bool bHasFoundAnswer = false;
unordered_map<int, vector<Wall>> m;
 
bool IsBlocked(int y, int x, int count) 
{
    if (m[x].size() == 0) return false;
 
    for (int i = 0; i < m[x].size(); ++i)
    {
        if (m[x][i].y + count == y)
        {
            return true;
        }
    }
 
    return false;
}
 
 
 
void DFS(int y, int x, int count)
{
    if (dp[y][x][count]) return;
 
    if (y == 0 && x == 7) // 우측상단 도착.
    {
        bHasFoundAnswer = true;
        return;
    }
 
    dp[y][x][count] = true;
 
    for (int i = 0; i < 9; ++i)
    {
        int nextY = y + dirs[i][0];
        int nextX = x + dirs[i][1];
 
        if (!IsInRange(nextY, nextX)) continue; // 범위 안인가?
        if (IsBlocked(nextY, nextX, count)) continue; // 이동하려는곳에 벽이 없는가?
        if (IsBlocked(nextY, nextX, count + 1)) continue; // 이동하려는 곳에 1초후에 벽이 내려오는가?
        
        DFS(nextY, nextX, count + 1);
 
        if (bHasFoundAnswer) return;
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 8; ++i)
    {
        for (int j = 0; j < 8; ++j)
        {
            char c;
            cin >> c;
 
            if (c == '#')
            {
                m[j].push_back({ i,j });
            }
        }
    }
 
    DFS(7, 0, 0);
    
    cout << bHasFoundAnswer;
}
 
 

 

간만에 풀어보는 알고리즘문제인데, 다행히 원트에 성공했다.

풀다보니 따로 배열에 입력값들을 저장해놓을 필요가 없어서 해당부분은 삭제했다.

 

이동할때마다 벽들이 아랫방향으로 한칸씩 움직인다.

유의해야할 점은, 이동이 먼저이다. 이동 후에 벽이 움직인다.

이동할 때 이동하려는 곳에 벽이 있으면 이동을 못한다.

그리고 이동후에 벽이 내려와서 같은칸에 겹치면, 더이상의 이동을 못한다.

 

즉, 기본적으로 이동하려는곳이 유효한지 (범위내에 있는지)는 기본적으로 체크해야하고 해당칸에 벽이 있는지, 거기에 더해서 1초후에 벽이 내려앉을 곳인지를 동시에 체크해줘야 한다.

 

그래서 이동하려하는 칸의 열에 해당하는 모든 벽들을 검사한다.

굳이 모든 벽들을 검사할 필요는 없다.어차피 벽은 아래로만 이동하기 때문에, 몇초가 지났는지만 알면 위치를 특정할 수 있다. 그래서 처음에 보드판을 입력받을 때 해쉬맵같은걸로 열값(x값)을 키값으로해서 저장했다.

 

77번째 라인이 현재시간 기준으로 이동하려는곳에 벽이있는가를 체크하는 것이고, 78번째가 이동 후에 벽이 내려오는가?를 체크하는것이다.

 

탐색하다 도착하면 정답을 찾았다고 표시하고 모든 루트에 대해 return 시키면 된다.

dp체크는 안해도 통과는 한다. 애초에 8*8짜리밖에 안되서..

체크를 하면 0ms대고, 안하면 8ms대가 나온다.