백준) 16985번: Maaaaaaaaaze in C

Made with Stable Diffusion

Problem

16985번: Maaaaaaaaaze

Solution

 

브루트 포스로 생성된 3차원 미로의 최단 거리(BFS)를 구하는 문제이다.

 

문제를 풀기 위한 알고리즘 구현은 크게 두 가지로 나눌 수 있다.

1) 문제에서 주어진 5개의 판을 가지고 5X5X5 미로 생성(브루트 포스),

2) 생성된 미로를 가지고 BFS를 통한 최단 거리 갱신.

 

1) 미로 생성

3차원 미로는 판의 쌓는 순서와 각 판의 회전에 대한 모든 경우를 구하여 생성했다.

 

먼저, 쌓는 순서는 판이 0부터 4까지 있고(배열의 index를 고려) 이는 0, 1, 2, 3, 4를 가지고 모든 순열(Permutation)을 만들어서 따로 저장했다.

생성되는 모든 순열의 개수는 5! = 5 * 4 * 3 * 2 * 1 = 120 개이다.

0, 1, 2, 3, 4

0, 1, 2, 4, 3

..

4, 3, 1, 2, 0

4, 3, 2, 1, 0

 

순열을 만드는 함수는 재귀함수로 구현했으며 아래와 같다.

// 재귀 함수를 통해 중복이 아닌 순열 생성. 
void permute(int l, int r) {
	int i;
    if (l == r) {
        for (i = 0; i <= r; i++) {
            plate_order[permute_count][i] = perm[i];
        }
        permute_count++;
    } else {
        for (i = l; i <= r; i++) {
            swap(&perm[i], &perm[l]);
            permute(l + 1, r);
            swap(&perm[i], &perm[l]);
        }
    }
}

초기에 "perm" 배열에는 0부터 4까지 차례대로 저장되어 있으며, l과 r이 같아질 때 "plate_order"라는 2차원 배열에 생성된 순열을 저장했다. 따라서 "plate_order"에는 총 120가지(5*4*3*2*1)의 순열이 저장된다.

 

그 다음 각 판을 회전시키는 모든 경우를 구현하기 위해서

먼저 특정한 판을 한 번 회전시켜주는 함수 "spin_plate()"와,

0부터 3까지 숫자를 가지고 모든 중복 순열을 생성해주는 "dup_permute()" 재귀함수를 구현하였다.

// 주어진 plate에 대해서 오른쪽으로 회전. 
void spin_plate(int plate_num){
	int i, j;
	int temp_plate[5][5];
	
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			temp_plate[j][4-i] = newmaze[plate_num][i][j];
		}
	}
	
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			newmaze[plate_num][i][j] = temp_plate[i][j];
		}
	}
};


// 재귀 함수를 통해 중복 순열 생성.
void dup_permute(int depth, int n, int k){
	int i;
	if(depth == k){
		for(i = 0; i < k; i++){
			spin_perm[dup_permute_count][i] = perm[i]; 
		}
		dup_permute_count++;
	}else{
		for(i = 0; i < n; i++){
			perm[depth] = i;
			dup_permute(depth+1, n, k);
		}
	}
}

중복 순열은 다음과 같이 생성된다.

0, 0, 0, 0, 0

0, 0, 0, 0, 1

..

3, 3, 3, 3, 2

3, 3, 3, 3, 3

위에서 각 순열은 첫번째 판부터 차례대로 판을 회전시키는 횟수를 의미한다.

(예를 들어, 0, 1, 0, 1, 0 이라면 2번째와 4번째 판을 한 번 회전)

모든 경우의 수는 4^5 = 1024 가 나온다.

이를 "spin_perm" 배열에 저장했다.

 

위에서 생성된 판의 순서와 회전 순열에 대해서 미로를 최종적으로 생성하기 위해

"make_new_maze()" 함수를 작성했다.

// 주어진 plate 회전 수열과 순서 수열에 대해서 새로운 미로 생성. 
// spin_i: 0 ~ 1023, order_i: 0 ~ 119
void make_new_maze(int spin_i, int order_i){
	int i, j, k;
	
	// 판을 순서에 맞게 만듬. 
	for(i=0; i<5; i++){
		for(j=0;j<5;j++){
			for(k=0;k<5;k++){
				newmaze[i][j][k] = maze[plate_order[order_i][i]][j][k];
			}
		}
	}
	
	// 각 판을 회전. 
	for(i=0; i<5; i++){
		for(j=0; j < spin_perm[spin_i][i]; j++){
			spin_plate(i);
		}
	}
};

이렇게 미로 생성을 완료한다.

 

 

2) 생성된 미로를 가지고 BFS.

 

생성된 3차원 미로의 한 꼭짓점에서 출발하고, 입구와 면을 공유하지 않는 꼭짓점, 즉 가장 먼 거리에 위치한 꼭짓점까지 이동하는 경로 중 최단거리를 구하기 위해 큐와 BFS 를 구현했다.

이때 문제에서는 참가자가 임의로 선택한 꼭짓점에서 출발한다고 나와있어서 8개의 꼭짓점을 모두 확인해야 할까 싶었지만 그럴 필요는 없었다.

3차원 미로의 위쪽 4개의 꼭짓점을 출발로 가정하나, 아래쪽 4개를 출발로 가정하나 구하는 최단 거리는 동일하고,

이미 먼저 생성된 미로의 모든 경우에, 미로의 형태는 동일하지만 전체적으로 회전된 미로들을 포함하고 있으므로,

출발점을 그냥 (x, y, z) = 0, 0, 0 좌표에서 시작하는 것으로만 고려했다.

 

위 BFS는 "minimum_distance_maze()" 함수를 통해 구현하였다.

 

결국 이 문제는

브루트 포스를 통해 모든 미로의 경우를 생성하고

BFS를 통해 3차원 미로의 최단 거리를 구할 수 있으면 풀 수 있는 문제이다.

 

Code

#include <stdio.h>

int maze[5][5][5]; // input 값으로 받는 미로.
int newmaze[5][5][5]; // 새롭게 생성된 미로.

int permute_count = 0, dup_permute_count = 0;
int perm[5] = {0, 1, 2, 3, 4}; // 순열 생성 위해 사용하는 배열. 
int plate_order[120][5]; // 0부터 4까지 모든 순열을 담는 변수. 
int spin_perm[1024][5]; // 0부터 3까지 모든 중복 순열을 담는 변수.

//Queue
#define Queue_size 999
int q[Queue_size][3];
int front, rear;

// BFS를 위한 앞, 뒤, 좌, 우, 상, 하 변화값. 
int dx[6] = {-1, 1, 0, 0, 0, 0};
int dy[6] = {0, 0, -1, 1, 0, 0};
int dz[6] = {0, 0, 0, 0, -1, 1};

void swap(int *a, int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
};

// 재귀 함수를 통해 중복이 아닌 순열 생성. 
void permute(int l, int r) {
	int i;
    if (l == r) {
        for (i = 0; i <= r; i++) {
            plate_order[permute_count][i] = perm[i];
        }
        permute_count++;
    } else {
        for (i = l; i <= r; i++) {
            swap(&perm[i], &perm[l]);
            permute(l + 1, r);
            swap(&perm[i], &perm[l]);
        }
    }
}

// 재귀 함수를 통해 중복 순열 생성.
void dup_permute(int depth, int n, int k){
	int i;
	if(depth == k){
		for(i = 0; i < k; i++){
			spin_perm[dup_permute_count][i] = perm[i]; 
		}
		dup_permute_count++;
	}else{
		for(i = 0; i < n; i++){
			perm[depth] = i;
			dup_permute(depth+1, n, k);
		}
	}
} 

// 주어진 plate에 대해서 오른쪽으로 회전. 
void spin_plate(int plate_num){
	int i, j;
	int temp_plate[5][5];
	
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			temp_plate[j][4-i] = newmaze[plate_num][i][j];
		}
	}
	
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			newmaze[plate_num][i][j] = temp_plate[i][j];
		}
	}
};

// 주어진 plate 회전 수열과 순서 수열에 대해서 새로운 미로 생성. 
// spin_i: 0 ~ 1023, order_i: 0 ~ 119
void make_new_maze(int spin_i, int order_i){
	int i, j, k;
	
	// 판을 순서에 맞게 만듬. 
	for(i=0; i<5; i++){
		for(j=0;j<5;j++){
			for(k=0;k<5;k++){
				newmaze[i][j][k] = maze[plate_order[order_i][i]][j][k];
			}
		}
	}
	
	// 각 판을 회전. 
	for(i=0; i<5; i++){
		for(j=0; j < spin_perm[spin_i][i]; j++){
			spin_plate(i);
		}
	}
};

// BFS와 큐를 이용, 최단 거리를 반환. 
int minimum_distance_maze(){
	int visited[5][5][5] = {0, };
	int i;
	
	front = 0;
	rear = 0;
	
	// 입구가 막혀있는 경우. 
	if(!newmaze[0][0][0])
		return -1;
	
	// 처음 위치 큐에 입력. 
	q[front][0] = 0;
	q[front][1] = 0;
	q[front][2] = 0;
	rear++;
	visited[0][0][0] = 1;
	
	while(front < rear){
		// 큐에서 값 가져옴.
		int x = q[front][0];
		int y = q[front][1];
		int z = q[front][2];
		front++;
		
		for(i=0;i<6;i++){
			// 새로 탐색할 위치 좌표 생성. 
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];
			
			// 3차원 미로 밖 위치 좌표 예외 처리. 
			if(nx < 0 || ny < 0 || nz < 0 || nx > 4 || ny > 4 || nz > 4)
				continue; 
				
			// 이미 방문했던 적이 있거나 벽이 있다면(0) 예외 처리. 
			if(visited[nx][ny][nz] || !newmaze[nx][ny][nz]) 
				continue;
			
			// 큐에 새로운 좌표 추가. 
			visited[nx][ny][nz] = visited[x][y][z] + 1;
			q[rear][0] = nx;
			q[rear][1] = ny;
			q[rear][2] = nz;
			rear++;
		}
	}
	
	// 최단 거리 반환. 
	return visited[4][4][4] - 1;
};

int main(){
	int i, j, k;
	
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			for(k=0;k<5;k++){
				scanf("%d", &maze[i][j][k]);
			}
		}
	}
	
	// 주어진 판들의 회전, 쌓는 순서 생성. plate_order와 spin_perm 갱신. 
	permute(0, 4);
	dup_permute(0, 4, 5);

	int distance;
	int minimum_distance = 999; 
	
	for(i=0;i<1024;i++){
		for(j=0;j<120;j++){
			make_new_maze(i, j);
			distance = minimum_distance_maze();
			if(distance != -1){ // 도달할 수 있고,
				if(distance < minimum_distance) // 최단 거리라면 갱신. 
					minimum_distance = distance;
			}
		}
	}
	
	// 최단거리를 찾지 못한 경우 -1 출력. 
	if(minimum_distance == 999)
		minimum_distance = -1;
		
	printf("%d", minimum_distance);
	
	return 0;
}