[백준] 16954 움직이는 미로 탈출 (java)

움직이는 미로 탈출 문제 풀어보기

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

문제

풀이

이 문제의 경우 고정된 체스판에서 왼쪽 아래에서 오른쪽 위로 올라갈 수 있는지 아닌 지를 확인하는 문제였다. 보드를 보자마자 bfs를 떠올렸고 바로 시도했다. 다른 bfs 최단거리 문제와 다르게 이문제는 최단거리가 아닌 도달 할 수 있는지 아닌지를 확인해야 하는 문제였다.

문제에서 주된 포인트는 3가지 정도였다.

1. 벽이 1초마다 아래로 움직인다. 맨 밑바닥이라면 사라진다.
2. 캐릭터가 움직이는 방향이 상하좌우 대각선으로 8가지 방향이다. 추가적으로 캐릭터가 그 위치 그대로 있는 경우도 존재한다.
3. bfs에서 시간이 지나가는 시점을 찾고 벽을 움직여야한다.

그래서 이 3가지에 구현 방법에 대해 설명해보자면

벽 움직임

처음에는 각각의 벽들을 list에 추가해 놓고 1초가 지나가는 지점에서 각각의 위치를 아래로 내리고 맨밑 바닥이라면 없애주는 방식으로 구현했었다.

그러나 이방식보다 어차피 벽이 움직이는 것이 전체 보드가 움직이는 것과 같다는 걸 알아챘다. 그리고 맨밑으로 가면 벽은 사라지기 때문에 맨 밑을 삭제하고 위에 빈 보드를 추가하는 방식으로 구현했다.

........      ........        ........
........      ........        ........
........      ........        ........
........      ........        ........
........   -> ........ 삭제 -> ........ 맨 위에 추가
........      ........        ........
#.......      #.......        ........
.#......                      #.......

이부분은 코드에서 moveWalls 메서드에서 확인할 수 있다.

캐릭터가 움직이는 방향

캐릭터가 움직이는 방향은 상하좌우 대각선 4가지 방향을 먼저 판단했다. 그래서 보드를 벗어나거나, 벽이 있는 경우, 방문한 경우를 제외하고는 큐에 추가해주었다.

그 이후 가만히 그 위치에 있는 경우를 추가해 주었는데 따로 판단해줄 것 없이 시간만 +1해서 큐에 추가해 주었다.

시간이 가는 시점

시간이 지나가는 부분은 현재 포인트를 큐에서 꺼냈을때 큐에 포인트에 관한 x, y, time을 저장해 두어서 현재의 curTime과 비교해서 다르다면 벽을 움직이는 방식으로 구현했다. 이후 보드의 상황이 바뀌었기 때문에 방문했던 상황을 저장해 두는 visited를 초기화해 주었다.

그리고 마지막으로 현재 위치에 벽이 오게 된다면 움직일 수 없기 때문에 continue해준다.

코드

참고자료

백준 움직이는 미로 탈출 풀러가기