16985 Maaaaaaaaaze

https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

 

1시간 20분 정도 걸려서 풀었다.

전에 풀었던 토마토와 비슷한 유형의 문제였다. 처음에 시간복잡도를 고려할 때 5비트 4진수의 가짓수인 1023에 판을 쌓는 경우의 수 120(5!)가지, 입구와 출구가 될 수 있는 가짓수 4가지... 등등 생각할 게 많아서 시간초과가 나지 않을까 걱정했는데 시간 제한이 2초로 널널해서 무난하게 통과할 수 있었다. 그래도 코드가 상당히 느려서 개선점을 찾아야 할 것 같다.

 

#include <bits/stdc++.h>
using namespace std;

int board1[7][7][7];
int board2[7][7][7];
int dist[7][7][7];
int dx[6]={1,0,-1,0,0,0};
int dy[6]={0,1,0,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int mn=0x7f7f7f7f;

void rotate(int dir,int board){
	//dir 방향, board 몇 번째로 입력된  판인지 
	while(dir--){
		int tmp[7][7];
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				tmp[i][j]=board2[board][i][j];
			}
		}
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				board2[board][i][j]=tmp[4-j][i];
			}
		}
	}
} 

int main(void){
	//입력  
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			for(int k=0;k<5;k++){
				cin>>board1[i][j][k];
				//Z Y X 순서 
			}
		}
	}

	for(int t=0;t<=1023;t++){ //t 1023으로 바꾸기 
		//board2에 board1 복사
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				for(int k=0;k<5;k++){
					dist[i][j][k]=-1;
					board2[i][j][k]=board1[i][j][k];
				}
			}
		}
		
		//5비트 4진수 생성 
		int brute=t;
		int pattern[5]={0,};
		for(int i=4;i>=0;i--){
			pattern[i]=brute%4;
			brute/=4;
		}
		
		//판 회전시키기 
		for(int j=0;j<5;j++){
			rotate(pattern[j],j);
		}
		
		//board2에 5개의 판을 쌓는 모든 경우를 돌아봄 (120가지)
		vector<int> permutation = {0,1,2,3,4};
		do{
			//board3에 원판을 쌓음
			int board3[7][7][7];
			for(int z=0;z<5;z++){
				for(int y=0;y<5;y++){
					for(int x=0;x<5;x++){
						board3[z][y][x]=board2[permutation[z]][y][x];
					}
				}
			} 
			
			
			//4가지 경우의 입/출구에 대해 BFS를 시행 
			vector<tuple<int,int,int>> arr={make_tuple(0,0,0),make_tuple(0,0,4),make_tuple(0,4,0),make_tuple(0,4,4)};
			for(int r=0;r<arr.size();r++){
				int sz,sy,sx; tie(sz,sy,sx)=arr[r]; //s :start
				int ez=4-sz,ey=4-sy,ex=4-sx; //e :end
				
				//시작과 끝 지점이 막혀있으면 시도하지 않음 
				if(board3[sz][sy][sx]==0||board3[ez][ey][ex]==0) continue;
				
				//dist 배열 초기화
				 for(int i=0;i<5;i++){
					for(int j=0;j<5;j++){
						for(int k=0;k<5;k++){
							dist[i][j][k]=-1;
						}
					}
				}
				
				//BFS
				queue<tuple<int,int,int>>Q;
				bool found=false;
				Q.push(make_tuple(sz,sy,sx)); dist[sz][sy][sx]=0;
				while(!Q.empty()){
					auto cur=Q.front(); Q.pop();
					int curZ,curY,curX; tie(curZ,curY,curX)=cur;
					if(curZ==ez&&curY==ey&&curX==ex){
						found=true;
						break;
					}
					for(int dir=0;dir<6;dir++){
						int nz=curZ+dz[dir];
						int ny=curY+dy[dir];
						int nx=curX+dx[dir];
						if(nx<0||ny<0||nz<0||nx>=5||ny>=5||nz>=5) continue;
						if(board3[nz][ny][nx]==0||dist[nz][ny][nx]!=-1) continue;
						Q.push(make_tuple(nz,ny,nx)); dist[nz][ny][nx]=dist[curZ][curY][curX]+1;
					}
				}
				
				//BFS를 마치고... 
				if(found) mn=min(mn,dist[ez][ey][ex]);
			}
			
		}while(next_permutation(permutation.begin(),permutation.end()));
	}
	if(mn==0x7f7f7f7f) mn=-1;
	cout<<mn<<'\n';
    return 0;
}