BOJ 16985. Maaaaaaaaaze

16985번: Maaaaaaaaaze (acmicpc.net)

16985번: Maaaaaaaaaze

3차원 배열을 이용한 문제다.

문제를 보면 바로 감이 오는데, backtracking과 bfs를 동시에 사용하는 문제다.

5*5 판을 회전하고 쌓는 부분은 backtracking으로,

경로 탐색은 bfs로 구현하면 된다.

 

먼저 90도를 돌려야 하는데 매번마다 돌리면 같은 배열을 계속해서 만들게 되므로 한번에 전부 돌려놓은 배열을 만들었다.

먼저 src를 전부 입력받은 후, 같은 크기의 배열 세개를 만들어 각각의 배열에 90도 180도 270도의 결과를 저장한다.

 

이후 permutation을 사용해 미로에 넣을 판의 순서를 결정하고

backtracking을 돌려서 넣어준 판의 모든 회전을 시도해본다.

그렇게 만들어진 판은 시작지점과 도착지점이 1일 때 (접근 가능할 때) BFS를 돌리면 된다.

 

backtracking이 아닌 products를 이용해서 회전을 처리했을 때는 약 2초가 더 걸렸다.