알고리즘 풀이/백준(Boj)
백준(BOJ) 16954번 움직이는 미로 탈출
100win10
2020. 1. 7. 14:33
문제 : https://www.acmicpc.net/problem/16954
16954번: 움직이는 미로 탈출
욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다. 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로
www.acmicpc.net
풀이 :
시간이 8초부터는 벽은 모두 내려간 상태고.(점)만 남은 상태가 된다. 이 상태에서는 무조건
목표지점(0,7)까지 갈수 있다.
따라서 3차원 배열 [시간][y좌표][x좌표] 로 bfs를 처리하자.
q에 담을 때에는 벽이라서 못가는 경우와 내려오는 벽에 닿는 경우는 걸러주어야 한다.
코드 ( C++ )