16954번 움직이는 미로 탈출

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

# 복습 # 추천 # bfs # 필수 # 코딩 # 코테 # 구현 # 생각

3차원 방문 visit 배열을 활용하는 문제이다.

주의할 점은 현재 위치에 서 있을 때는 방문 처리 여부와는 상관 없이 무조건 queue에 넣어야 한다.

이유는 어떠 한 경우에서 (r, c)에서 현재 위치에 서 있었을 때, 방문 처리를 하면, 다른 경우에서 (r, c)에 대해 그 자리에 있을 수 없다.

이 외에는 방문 처리를 이동 방향에 따라 표시해준다.

visit[행][열][이동 방향] = 어느 방향에서 (행, 열)로 왔는지 방문 처리

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 9
 
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
 
bool visit[Max][Max][Max];
/*
3번 째 배열 인덱스
0 ~ 7 : 상하좌우, 대각선
*/
 
typedef struct info
{
    int y, x;
    vector<vector<string> > Map;
};
 
// 맵을 아래로 한 칸 내려가게 하고, 내린 맵을 반환
vector<vector<string> > Move(vector<vector<string> > v)
{
    vector<string> temp = { "........" };
    vector<vector<string> > ret = { temp };
 
    for (int i = 0; i < v.size() - 1; i++) {
        vector<string> t;
        for (auto j : v[i]) {
            t = { j };
        }
        ret.push_back(t);
    }
 
    return ret;
}
 
int bfs(vector<vector<string> > v)
{
    queue<info> q;
    q.push({ 7, 0, v });
    for (int i = 0; i < 9; i++) {
        visit[7][0][i] = true;
    }
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().y;
            int c = q.front().x;
            vector<vector<string> > temp = q.front().Map;
 
            q.pop();
 
            // 도착
            if (r == 0 && c == 7) {
                return 1;
            }
 
            // 현재 욱제의 위치가 벽이라면 무시
            if (temp[r][0][c] == '#') {
                continue;
            }
 
            vector<vector<string> > t;
 
            // 욱제 이동
            for (int i = 0; i < 8; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= 8 || x < 0 || x >= 8 || visit[y][x][i] || temp[y][0][x] == '#') {
                    continue;
                }
 
                visit[y][x][i] = true;
                t = Move(temp);
                q.push({ y, x, t });
            }
 
            // 움직이지 않고, 현재 위치에 서 있기.
            t = Move(temp);
            q.push({ r, c, t });
        }
    }
 
    return 0;
}
 
int main()
{
    cin.tie(0);
 
    vector<vector<string> > v;
 
    for (int i = 0; i < 8; i++) {
        string s;
        cin >> s;
        vector<string> temp = { s };
        v.push_back(temp);
    }
 
    printf("%d\n", bfs(v));
 
    return 0;
}