BOJ 16985번 Maaaaaaaaaze 문제 자바(java) 풀이
문제정리
- 3차원 미로 탈출 대회 개최
- 5x5 크기의 판이 5개 주어진다.
- 하얀색 칸은 참가자가 들어갈 수 있는 칸, 검은 칸은 못들어가는 칸이다.
- 참가자는 주어진 판들을 시계 or 반시계 방향으로 자유롭게 회전할 수 있다. 뒤집을 수는 없다.
- 회전을 완료한 후 참가자는 판 5개를 쌓는다. 쌓는 순서는 참가자 마음대로 한다.
- 입구는 참가자가 임의로 선택한 꼭지점. 출구는 입구와 면을 공유하지 않는 꼭짓점
- 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 승리한다.
- 입구에서 출구로 도달할 수 있는 방법이 없는 경우 탈출이 불가능 하다.
문제 풀이
이 문제는 정말 고려해야할 점이 많습니다. 그리고 문제를 잘 읽어야 합니다.
처음에 판을 임의 순서로 쌓는것을 정리해 놓고도 그걸 적용안해서 헤맸네요 ㅠㅠㅠ
- 쌓는 순서는 우리 맘이기 때문에 순열을 고려해주어야 합니다.
기본적인 순열의 형태로 순서를 생각합니다. 순서는 order 배열에
담습니다.
만약 배열이 [0,1,4,3,2]가 된다면 0번째 판을 첫번째 그대로 두고 1번째 판을 두번째, 4번째 판을 3번째에, 3번째 판을 4번째에 2번째 판을 5번째에 둡니다.
- 모든 회전을 고려해야 합니다.
저는 정말 간단하게 5중 for문을 이용하여 회전하는 모든 경우의 수를 따져주었습니다.
rotate(i) 함수는 i번째 판을 시계방향으로 90도 만큼 회전시키는 함수입니다.
- bfs를 통해 탐색합니다.
일반적인 bfs 함수와 똑같이 작성하면 됩니다.
만약에 0,0,0과 4,4,4가 1이 아니라면 애초에 시작과 도착을 할 수 없으므로 이 경우는 그냥 넘어갑니다.
(4,4,4)에 도착하였다면 min 값을 update 해줍니다.
백준 16985번 자바(java) 코드
- 실행 시간: 1276 ms
- 메모리: 294136 kb