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. 내 코드
| #include <iostream> | |
| #include <string> | |
| #include <climits> | |
| #include <queue> | |
| using namespace std; | |
| int arr[5][5][5] = {0, }; | |
| int tmpArr[5][5][5] = {0, }; | |
| int dx[6] = {0, 0, 1, 0, 0, -1}; | |
| int dy[6] = {0, 1, 0, 0, -1, 0}; | |
| int dz[6] = {1, 0, 0, -1, 0, 0}; | |
| int minVal = INT_MAX; | |
| bool dfsVisit[5] = {0, }; | |
| typedef struct{ | |
| int x, y, z; | |
| int len; | |
| }Q_ELEM; | |
| void copy_arr(string s){ | |
| for (int i = 0; i < 5; i++) { | |
| for (int j = 0; j < 5; j++) { | |
| for (int k = 0; k < 5; k++) { | |
| tmpArr[i][j][k] = arr[s.at(i) - '1'][j][k]; | |
| } | |
| } | |
| } | |
| } | |
| int get_min(int a, int b){ | |
| return a < b ? a : b; | |
| } | |
| void turn_right(int idx){ | |
| // 임시 복사 배열 tmpArr에 해당 층 미로 90도 회전 | |
| int tmp2dArr[5][5] = {0, }; | |
| for (int i = 0; i < 5; i++) { | |
| for (int j = 0; j < 5; j++) { | |
| tmp2dArr[j][4-i] = tmpArr[idx][i][j]; | |
| } | |
| } | |
| for (int i = 0; i < 5; i++) { | |
| for (int j = 0; j < 5; j++) { | |
| tmpArr[idx][i][j] = tmp2dArr[i][j]; | |
| } | |
| } | |
| } | |
| bool available(int x, int y, int z){ | |
| return x >= 0 && y >= 0 && z >= 0 && x < 5 && y < 5 && z < 5; | |
| } | |
| void bfs_maze(){ | |
| // BFS로 3차원의 미로를 탐사하는 함수 | |
| queue<Q_ELEM> bfsQ; | |
| bool visit[5][5][5] = {0, }; | |
| Q_ELEM elem; | |
| // 시작 좌표 (0,0,0)에서 끝 좌표 (4,4,4)에 도달할 때까지 탐사 | |
| elem.x = elem.y = elem.z = elem.len = 0; | |
| bfsQ.push(elem); | |
| while(!bfsQ.empty()){ | |
| Q_ELEM topElem = bfsQ.front(); | |
| bfsQ.pop(); | |
| if(topElem.x == 4 && topElem.y == 4 && topElem.z == 4){ | |
| minVal = get_min(minVal, topElem.len); | |
| } else { | |
| for (int i = 0; i < 6; i++) { | |
| int nextX = topElem.x + dx[i]; | |
| int nextY = topElem.y + dy[i]; | |
| int nextZ = topElem.z + dz[i]; | |
| // 다음 좌표가 범위에서 벗어나지 않고, 갈 수 있는 위치(1)이며, 방문되지 않은 경우(사이클 X) 큐에 삽입 | |
| if(available(nextX, nextY, nextZ) && tmpArr[nextX][nextY][nextZ] != 0 && !visit[nextX][nextY][nextZ]){ | |
| Q_ELEM pushElem; | |
| pushElem.x = nextX; | |
| pushElem.y = nextY; | |
| pushElem.z = nextZ; | |
| pushElem.len = topElem.len+1; | |
| bfsQ.push(pushElem); | |
| visit[nextX][nextY][nextZ] = true; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| void dfs_turn(string s){ | |
| // 각 층의 미로에 대해서 →, ↓, ←, ↑ 각 방향에 대해서 돌리는 조합을 구하는 함수 | |
| if(s.size() == 5){ | |
| if(minVal == 12) return; // 미로탐색 경로중 최적인 12가 먼저 계산되면 더이상 탐사 중지 | |
| else { | |
| for (int i = 0; i < s.size(); i++) { | |
| for (int j = 0; j < s.at(i) - '0'; j++) { | |
| turn_right(i); // 각 층에 대해서 모든 돌리는 경우의 수를 시뮬레이션 (4^4^4^4^4가지) | |
| } | |
| if(tmpArr[0][0][0] == 1 && tmpArr[4][4][4] == 1) bfs_maze(); // 미로의 처음과 끝이 진입 가능한 경우 BFS 탐사 시작 | |
| } | |
| } | |
| } else { | |
| for (int i = 0; i < 4; i++) { | |
| string nextC(1, i + '0'); | |
| dfs_turn(s + nextC); | |
| } | |
| } | |
| } | |
| void dfs_layer(string s){ | |
| // 5층의 미로를 쌓는 조합을 만드는 함수 | |
| // 스트링의 엔트리의 각 문자는 해당 미로 층의 위치를 나타낸다. | |
| if(s.size() == 5){ | |
| // 조합이 만들어진 경우, 해당 모양으로 미로를 쌓아 tmpArr에 복사 | |
| copy_arr(s); | |
| if(minVal == 12) return; // 미로탐색 경로중 최적인 12가 먼저 계산되면 더이상 탐사 중지 | |
| else dfs_turn(""); // 각 미로의 층들을 돌리며 DFS 탐사하는 함수 호출 | |
| } else { | |
| for (int i = 0; i < 5; i++) { | |
| if(!dfsVisit[i]) { | |
| string nextC(1, i + '1'); | |
| dfsVisit[i] = true; | |
| dfs_layer(s + nextC); | |
| dfsVisit[i] = false; | |
| } | |
| } | |
| } | |
| } | |
| int main(){ | |
| // 모두 0이거나 1인 경우 답이 바로 계산되므로 알고리즘 호출부에서 제외한다. | |
| bool allZeros = true; | |
| bool allOnes = true; | |
| for (int i = 0; i < 5; i++) { | |
| for (int j = 0; j < 5; j++) { | |
| for (int k = 0; k < 5; k++) { | |
| cin >> arr[i][j][k]; | |
| allZeros &= (arr[i][j][k] == 0); | |
| allOnes &= (arr[i][j][k] == 1); | |
| } | |
| } | |
| } | |
| if (allZeros) { | |
| cout << -1 << endl; | |
| } else if (allOnes) { | |
| cout << 12 << endl; | |
| } else { | |
| dfs_layer(""); | |
| if(minVal == INT_MAX) cout << -1 << endl; | |
| else cout << minVal << endl; | |
| } | |
| return 0; | |
| } |
* 유의점 : 알고리즘 구현시 메모리 사용에 대한 고찰
알고리즘 구현을 완료하고 백준 사이트에 프로그램 제출 시, 계속 타임아웃이 발생하는 현상이 발생했었다. 나중에 알고보니 3차원 배열을 매번 벡터로 새로 만들어 계산했었는데, 이 부분에서 자원소모가 크게 발생하여 병목이 생긴 것이었다.
생각해보니 같은 형식으로 계산을 하는 경우 굳이 매번 새로 메모리에 벡터를 할당해 줄 필요는 없었다. 전역으로 3차원 배열을 매번 덮어쓰며 계산하니 매우 간단하게 해결할 수 있는 문제였던 것.
