A. 문제설명
https://www.acmicpc.net/problem/16985
문제에 대한 자세한 설명은 링크 참조
1. 5*5 크기 판이 5개 주어짐
2. 각 판에는 들어갈 수 있는 칸과 들어갈 수 없는 칸이 구분됨
3. (0,0,0)에서 시작하여 (4,4,4)로 도착하는 경로 탐색
4. 각 판은 90도씩 360도 시계/반시계 방향으로 전부 돌릴 수 있으나 뒤집는 것은 허용되지 않음
5. 회전을 완료한 후, 5개의 판을 쌓음. 이 때 판을 쌓는 조합은 바뀌어도 됨
6. 모든 경우를 탐사해보아도 끝점에 도달불가한 경우 -1 출력, 끝점에 도달 가능한 경우 최적의 경로를 구하라
B. 접근법
DFS(조합구하기) + BFS(경로탐색)
먼저 문제의 조건들을 정리하면 5*5*5의 3차원 정육면체의 공간에서 (0,0,0)에서 (4,4,4)에 도달하는 경로 탐색이 목표.
각 판은 회전될 수 있고, 또 각 판을 쌓는 방법은 모두 달라질 수 있음
→ 따라서, 5개 판의 →, ↓, ←, ↑ 방향 회전을 고려한 모든 조합: DFS
→ 5개 판을 쌓는 모든 조합: DFS
그리고, 마지막으로 미로를 탐사하여 경로탐색하는 알고리즘은 BFS로 구현하도록 한다.
C. 풀이
1. 먼저, 모두 0이거나 1인 경우 답이 바로 계산되므로 알고리즘 호출부에서 제외한다.
2. 5층의 판을 쌓는 조합을 만듦 - dfs_layer()
3. 미로탐색 경로중 최적인 12가 먼저 계산되면 더이상 탐사 중지하고, 아닌경우 각 미로의 층들을 돌리며 DFS 탐사하는 함수 호출
4. 2에서 5층 판의 조합이 구해진 경우 각 층의 미로에 대해서 →, ↓, ←, ↑ 각 방향에 대해서 돌리는 조합을 구함 - dfs_turn()
6. 모든 판을 각각 전부 돌려 경우의 수를 시뮬레이션 (4^4^4^4^4가지)
7. 미로의 처음과 끝이 진입 가능한 경우 BFS 탐사 시작 - bfs_maze()
8. BFS에 첫 탐사 위치를 큐에 넣고, 큐가 빌 때까지 너비우선탐색 수행
9. 다음 좌표가 범위에서 벗어나지 않고, 갈 수 있는 위치(1)이며, 방문되지 않은 경우(사이클 X) 큐에 삽입
10. 끝 점에 도달한 경우 도달시 걸린 시간을 최소시간과 비교하여 더 작을 시 업데이트
D. 내 코드
* 유의점 : 알고리즘 구현시 메모리 사용에 대한 고찰
알고리즘 구현을 완료하고 백준 사이트에 프로그램 제출 시, 계속 타임아웃이 발생하는 현상이 발생했었다. 나중에 알고보니 3차원 배열을 매번 벡터로 새로 만들어 계산했었는데, 이 부분에서 자원소모가 크게 발생하여 병목이 생긴 것이었다.
생각해보니 같은 형식으로 계산을 하는 경우 굳이 매번 새로 메모리에 벡터를 할당해 줄 필요는 없었다. 전역으로 3차원 배열을 매번 덮어쓰며 계산하니 매우 간단하게 해결할 수 있는 문제였던 것.
