백준(BOJ) 16985 Maaaaaaaaaze C++ 풀이

문제 링크: https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

풀이에 이용된 알고리즘: BFS, 순열(DFS), Brute Force

 

삼성 전자 코딩 테스트 기출 문제 풀이를 진행했거나 최근 bfs, dfs 등을 공부하는 사람에게는 익숙한 미로 탐색 유형이다.

 

아... 미로 탐색 유형이 익숙하다는 것이고, 16985 문제의 경우는 익숙하지 않은 미로 탐색처럼 느껴질 수 있다고 생각된다.

 

일단 단순히 미로를 탐색하는 것이 아니라, 미로를 제작도 우리가 해야한다....

 

그리고 제작된 미로를 탐색하여 최단 거리를 구하는데, 각 미로별 최단 거리 중에서 가장 작은 값을 출력하는 것이 이 문제의 목표이다.

 

따라서 제작 가능한 모든 미로를 만들고, 각각에 대해서 최단 거리 탐색 즉 bfs를 적용하는 brute force 방법으로 문제를 풀었다

 

미로 제작은, 미리 준비된 5개의 판의 순서를 임의로 정해서 쌓아주면(3차원 틀에 판을 삽입하는 것으로 생각했다.) 3차원 미로가 완성된다. --> select_arr 함수 구현

 

이 때, 판은 시계 방향 또는 반시계 방향 90도 단위로 자유롭게 회전이 가능하다. --> rotate_arr 함수 구현

 

모든 경우의 미로 제작을 위해서 상기 내용을 dfs로 구현한다.

 

그리고 미로 탐색은 일반적인 2차원 미로에서 x y 방향뿐 아니라, z축 방향을 고려해야하므로 dz, dx, dy를 다음과 같이 구현하였다.

 

int dz[] = {0, 0, 0, 0, -1, 1};

int dx[] = {-1, 0, 1, 0, 0, 0};

int dy[] = {0, 1, 0, -1, 0, 0};

 

dfs로 5개의 판 모두를 선택하여 3차원 틀에 넣어주면 즉, 5개의 판을 선택한 후에는(selected 배열 이용) 시작점 (1, 1, 1)에서 도착점 (5, 5, 5)까지의 최단 거리를 파악하고 현재 ans보다 작은 값이라면 갱신하도록 한다.

 

(이 때, 시작점 (1, 1, 1)이 이동 가능한 칸인지도 꼭 확인해주어야 한다!)

 

/* BOJ 16985 Maaaaaaaaaze */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int maze[6][6][6], parts[6][6][6], selected[6], visited[6][6][6];
int dz[] = {0, 0, 0, 0, -1, 1};
int dx[] = {-1, 0, 1, 0, 0, 0};
int dy[] = {0, 1, 0, -1, 0, 0};
const int INF = 1e9;
int ans = INF;
 
void rotate_arr(int h_idx) // 90도 시계 방향 회전
{
    int tmp[6][6];
    for (int i = 1; i <= 5; i++)
        for (int j = 5; j > 0; j--)
            tmp[j][5 - i + 1] = maze[h_idx][i][j];
 
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            maze[h_idx][i][j] = tmp[i][j];
}
 
void select_arr(int h_idx, int part_num) // '판'을 선택하여 미로의 h_idx 층에 삽입
{
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            maze[h_idx][i][j] = parts[part_num][i][j];
}
 
typedef struct NODE
{
    int x, y, z;
    NODE(int _z, int _x, int _y)
    {
        z = _z, x = _x, y = _y;
    }
} NODE;
 
int bfs()
{
    memset(visited, 0xff, sizeof(visited));
    queue<NODE> q;
    q.push({1, 1, 1});
    visited[1][1][1] = 0;
 
    while (!q.empty())
    {
        int z = q.front().z;
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
 
        for (int i = 0; i < 6; i++)
        {
            int nz = z + dz[i], nx = x + dx[i], ny = y + dy[i];
            if (visited[nz][nx][ny] == -1 && maze[nz][nx][ny] == 1)
            {
                q.push({nz, nx, ny});
                visited[nz][nx][ny] = visited[z][x][y] + 1;
            }
        }
    }
 
    return visited[5][5][5];
}
 
void dfs(int h_idx)
{
    if (h_idx > 5)
    {
        // 미로 탐색 시작
        // 최소값 갱신
        if (maze[1][1][1] == 1) // (1, 1, 1)이 0이면 아예 미로 탐색 시작 조차 불가능
        {
            int move_cnt = bfs(); // (5, 5, 5)까지 탐색 진행
            if (move_cnt != -1)
                ans = min(ans, move_cnt);
        }
        return;
    }
 
    for (int i = 1; i <= 5; i++)
    {
        if (!selected[i])
        {
            selected[i] = true;   // i번째 '판' 선택
            select_arr(h_idx, i); // 미로의 h_idx 층에 i번째 '판'을 삽입
 
            for (int d = 0; d < 4; d++) // 회전
            {
                rotate_arr(h_idx); // 미로의 h_idx 층을 90도 시계 방향 회전
                dfs(h_idx + 1);
            }
 
            selected[i] = false;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    int num = 1;
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            for (int k = 1; k <= 5; k++)
                cin >> parts[i][j][k];
 
    dfs(1);
 
    cout << ((ans == INF) ? -1 : ans) << endl;
 
    return 0;
}