문제
욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.
이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.
1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.
욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.
입력
8개 줄에 걸쳐서 체스판의 상태가 주어진다.'.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.
........
........
........
........
........
........
##......
........
출력
욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.
0
문제 접근
문제는 간단한 BFS/DFS 문제이다. 하지만 조금 다른건 어떻게 시간에 따른 방문을 구현해 낼것이냐 의 문제로 초점을 맞출 수 있다. 처음 생각은 boj 안전영역 문제 처럼 매번 board를 새로 그리고 bfs 하려 했으나 문제가 더 복잡해지고 예외처리도 많아져 답이 틀리게 도출 됐다. 결국 이 문제에서 내가 가져가야할 것은
int visited[9][8][8]; 삼차원 방문 배열이다.
시간이 흐르면서 해당 초에 어디에 위치에 해야하는지 true/false로 표현할 수 있다. 내가 이동 후 벽이 내려오니까 내가 옮겨가야할 위치에 벽이 있지 않고, 내 위에 벽만 없으면 그 칸으로 이동할 수 있다는 소리이다. (그리고 vector/queue 를 사용시에 값 3개를 저장하고 싶으면 tuple 보다는 구조체가 편하다)
int bfs()
{
std::queue<Pos>q;
q.push({ 0,7,0 });
visited[0][7][0] = 1;
while (!q.empty())
{
int t = q.front().t;
int x = q.front().x;
int y = q.front().y;
q.pop();
if (x == 0)return 1;
for (int i = 0; i < 9; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
int nt = t + 1;
if (t >= 8) return 1;
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
if (nx - t >= 0 && board[nx - t][ny] == '#' )continue;
if (nx - t - 1>= 0 && board[nx - t -1 ][ny] == '#' ) continue;
if (visited[nt][nx][ny] == 0)
{
visited[nt][nx][ny] = 1;
q.push({ nt, nx,ny });
}
}
}
return 0;
}전체코드
#include <iostream>
#include <vector>
#include <queue>
char board[8][8];
int dx[] = { 1,0,-1,0,1,-1,1,-1,0 };
int dy[] = { 0,1,0,-1,1,-1,-1,1,0 };
int visited[9][8][8];
struct Pos
{
int t;
int x;
int y;
};
int bfs()
{
std::queue<Pos>q;
q.push({ 0,7,0 });
visited[0][7][0] = 1;
while (!q.empty())
{
int t = q.front().t;
int x = q.front().x;
int y = q.front().y;
q.pop();
if (x == 0)return 1;
for (int i = 0; i < 9; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
int nt = t + 1;
if (t >= 8) return 1;
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
if (nx - t >= 0 && board[nx - t][ny] == '#' )continue;
if (nx - t - 1>= 0 && board[nx - t -1 ][ny] == '#' ) continue;
if (visited[nt][nx][ny] == 0)
{
visited[nt][nx][ny] = 1;
q.push({ nt, nx,ny });
}
}
}
return 0;
}
int main()
{
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
std::cin >> board[i][j];
}
}
int answer = bfs();
std::cout << answer << std::endl;
return 0;
}```