[ 백준 ] 16954 / 움직이는 미로 탈출
# 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;
}
Author And Source
이 문제에 관하여([ 백준 ] 16954 / 움직이는 미로 탈출), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-16954-움직이는-미로-탈출
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* 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
* - 벽이 떨어져서 사라질 수 있다는 점을
* 빼먹지 말고 잘 다루어주자
*/
//
// 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;
}
Author And Source
이 문제에 관하여([ 백준 ] 16954 / 움직이는 미로 탈출), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-16954-움직이는-미로-탈출저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)