[ 백준 ] 16954 / 움직이는 미로 탈출

18804 단어 psbojboj

# Appreciation

/*
 * Problem :: 16954 / 움직이는 미로 탈출
 *
 * Kind :: BFS
 *
 * Insight
 * - 벽이 움직인다(=떨어진다)
 *   + 벽이 떨어지는 것을 직접 구현할 수도 있지만...
 *     흐른 시간을 알면 굳이 실제로 벽을 떨어뜨리지 않고도
 *     갈 수 있는 칸인지 없는 칸인지 알 수 있을 것 같다
 *     # 초기 벽이 있는 칸이 (i, j) 였다면
 *       t 초가 흐른 후의 위치는 (i+t, j) 이다
 *       맨 왼쪽 위 칸을 (0, 0) 이라고 하면,
 *       i+t > 7 인 경우, 벽이 떨어져서 사라진 것을 뜻한다
 *       -> 벽이 떨어지지 않았다면, 벽은 (i+t, j) 에 있고
 *          다시 1초가 흐르면 (i+t+1, j) 에 있게 된다
 *          이때도 i+t+1 > 7 인 경우, 벽이 떨어져서 사라진 것을 뜻한다
 *
 * - 욱제의 캐릭터가 현재 있는 칸을 (y, x) 로, 현재 흐른 시간을 t 초라고 하자
 *   이제 다음 칸 (ny, nx) 로 움직이려고 한다
 *   + 이때, (ny, nx) 는 벽칸이 아니어야 하는데
 *     이는 초기 주어진 벽의 상태를 기준으로 (ny-t, nx) 가 벽칸이 아니라는 것을 뜻한다
 *     # ny-t < 0 이면 벽이 있더라도 떨어져서 빈 칸이 된다
 *     또한, (ny-1, nx) 는 벽칸이 아니어야 하는데 <= 이동하면 1초후 떨어지는 이 벽에 죽음
 *     이는 초기 주어진 벽의 상태를 기준으로 (ny-(t+1), nx) 가 벽칸이 아니라는 것을 뜻한다
 *     # ny-(t+1) < 0 이면 벽이 있더라도 떨어져서 빈 칸이 된다
 *       -> 이러한 점들을 생각하면서 문제를 풀어나가도록 하자
 *
 * - 벽이 떨어지는 조건 외에는
 *   전형적인 BFS 문제이다
 *
 * Point
 * - 벽이 떨어져서 사라질 수 있다는 점을
 *   빼먹지 말고 잘 다루어주자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
char board[8][8];
struct Point { int y, x; };
int dy[9] = {-1, -1, -1,  0,  0,  0, +1, +1, +1};
int dx[9] = {-1,  0, +1, -1,  0, +1, -1,  0, +1};

// Set up : Functions Declaration
bool isValid(int y, int x);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    for (int i=0; i<8; i++) {
        for (int j=0; j<8; j++) {
            cin >> board[i][j];
        }
    }

    // Process
    queue<Point> que;
    bool isVisited[8][8];
    que.push({7, 0});

    int time = 0; /* 흐른 시간 */
    while (not(que.empty())) {
        int size = que.size();
        /* time 초 흘렀을 때 기준으로 초기화 */
        memset(isVisited, false, sizeof(isVisited));
        while (size--) { /* 이 반복문 동안 다루는 욱제 캐릭터의 위치는 모두 time 초 흐른 상태 */
            int cy = que.front().y; /* 욱제 캐릭터의 현재 y 좌표 */
            int cx = que.front().x; /* 욱제 캐릭터의 현재 x 좌표 */
            que.pop();

            // Control : Output
            if (cy == 0 && cx == 7) { /* 가장 오른쪽 윗칸 도착하면 */
                cout << 1 << endl;
                exit(0);
            }

            for (int i=0; i<9; i++) {
                int ny = cy + dy[i]; /* 욱제 캐릭터의 다음 y 좌표 */
                int nx = cx + dx[i]; /* 욱제 캐릭터의 다음 x 좌표 */
                /* 욱제 캐릭터의 다음 좌표가 유효하고 time 초 흐른 상황에서 방문한 적이 없으며 */
                if (isValid(ny, nx) && not(isVisited[ny][nx])) {
                    /* time 초 흐른 상황에서 다음 좌표가 빈칸이고 */
                    if (ny-time < 0 || board[ny-time][nx] == '.') {
                        /* time 초 흐른 상황에서 다음 좌표의 윗칸이 빈칸이면 */
                        if (ny-(time+1) < 0 || board[ny-(time+1)][nx] == '.') {
                            /* 다음 좌표로 이동 */
                            isVisited[ny][nx] = true; /* 방문처리 */
                            que.push({ny, nx}); /* Queue 에 다음 좌표를 넣어줌 */
                        }
                    }
                }
            }
        }
        time++; /* 시간의 흐름 갱신 */
    }

    // Control : Output
    cout << 0 << endl; /* 가장 오른쪽 윗 칸에 도착 못함 */
}

// Helper Functions
bool isValid(int y, int x)
/* 주어진 좌표가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < 8 && x >= 0 && x < 8;
}

좋은 웹페이지 즐겨찾기