문제

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

풀이

조건

• 입력 받은 5개의 판을 적절히 회전시켜 랜덤으로 쌓은 뒤 미로 탈출의 최단 거리를 구해야한다.
• 입구 map[0][0][0] 에서 출구 map[4][4][4] 까지 길이 이어져 있어야 한다.
  • 입구와 출구의 위치는 위의 좌표로 정해져 있다.
• 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.
  • -1 을 출력함.
• 입력값 1은 길, 0은 벽이다.

풀이 순서

• 3차원 배열인 map 에 입력값을 받는다.
• 백트래킹을 사용하여 판을 회전하는 조합을 구한다.
  • 조합이 완료되면 판을 쌓는 연산을 수행한다.
• 백트래킹을 사용하여 판을 쌓는 조합이 완료되면 BFS를 사용해 최단거리를 구한다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static final int INF = 987654321; // 탈출할 수 있는지 구분할 상수
    static final int N = 5; // 판과 미로의 크기
    static int MIN = INF; // 구해야 할 최솟값
    
    static boolean[] visitFloor = new boolean[N]; // 백트래킹 시 사용할 체크배열
    static int[][][] map = new int[N][N][N]; // 3차원 배열(미로)
    
    static List<Integer> floorList = new ArrayList<>(); // 쌓을 때 쓸 리스트
    
    static int[] dz = {-1, 1, 0, 0, 0, 0};
    static int[] dy = {0, 0, -1, 1, 0, 0};
    static int[] dx = {0, 0, 0, 0, 1, -1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st;
        for (int h = 0; h < N; h++) {
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[h][i][j] = Integer.parseInt(st.nextToken());
                }
            }
        }
        
        searchMinPath(0);
 
        if (MIN == INF)
            System.out.println(-1);
        else
            System.out.println(MIN);
    }
    
    // 회전 정하기
    static void searchMinPath(int depth) {
        if (depth == 5) {
        	// 쌓는 순서 정하기
            stackFloor(0);
            return;
        }
        for (int i = 0; i <= 3; i++) {
        	// 해당 판을 90도 회전하고 다음 판에 대해 재귀 호출
            rotate(depth);
            searchMinPath(depth + 1);
        }
    }
    
    // 쌓는 순서 정하기
    static void stackFloor(int idx) {
        if (idx == N) {
            bfs();
            return;
        }
        
        for (int i = 0; i < N; i++) {
            if (!visitFloor[i]) {
            	visitFloor[i] = true; // 방문한 판 방문 처리
                
                floorList.add(i); // 리스트에 넣음
                stackFloor(idx + 1); // 재귀 호출
                
                floorList.remove(floorList.size() - 1); // 다음 for문을 위해 리스트의 마지막 값을 없앰
                
                visitFloor[i] = false; // 다음 for문을 위해 방문 취소 함
            }
            
        }
    }
 
    // 탐색하며 최단 거리 구하기
    private static void bfs() {
    	// 탐색할 미로
        int[][][] updateMap = new int[N][N][N];
        
        // 쌓는 순서에 따라 쌓고 bfs
        for (int i = 0; i < N; i++) {
            System.arraycopy(map[floorList.get(i)], 0, updateMap[i], 0, map[floorList.get(i)].length);
        }
        
        // 입구와 출구에 길이 없으면 바로 종료
        if (updateMap[0][0][0] == 0 || updateMap[4][4][4] == 0) return;
 
        boolean[][][] visit = new boolean[N][N][N]; // 방문 체크할 배열
        visit[0][0][0] = true;
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(0, 0, 0, 0));
 
        while (!q.isEmpty()) {
            Pos p = q.poll();
            
            int z = p.z;
            int y = p.y;
            int x = p.x;
            int dist = p.dist;
            
            // 탈출구로 도달하면 종료
            if (z == 4 && y == 4 && x == 4) {
                if (MIN > dist) {
                    MIN = dist;
                }
                continue;
            }
 
            for (int d = 0; d < 6; d++) {
                int nz = z + dz[d];
                int ny = y + dy[d];
                int nx = x + dx[d];
                
                // 범위 벗어나면 넘어감
                if (nz < 0 || nz >= N || ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
                
                // 이미 방문했거나 벽이면 넘어감
                if (visit[nz][ny][nx] || updateMap[nz][ny][nx] == 0) continue;
                
                visit[nz][ny][nx] = true;
                q.add(new Pos(nz, ny, nx, dist + 1));
            }
        }
    }
 
    // 90도 회전 시킴
    static void rotate(int idx) {
        int[][] temp = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                temp[i][j] = map[idx][N - j - 1][i];
            }
        }
        System.arraycopy(temp, 0, map[idx], 0, temp.length);
    }
    
    static class Pos {
        int z;
        int y;
        int x;
        int dist;
 
        Pos(int z, int y, int x, int dist) {
            this.z = z;
            this.y = y;
            this.x = x;
            this.dist = dist;
        }
    }
 
}

정리

• System.arraycopy()를 사용하여 쉽게 복사 배열을 얻을 수 있었다.
• 처음에 풀이할 때 불필요한 연산이 많아 코드가 길어지고 복잡했는데 수정하여 깔끔하게 해결했다.