[BOJ - JAVA] 16985 - Maaaaaaaaaze (구현, 그래프, 완전탐색, BFS)

# 주소

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

16985번: Maaaaaaaaaze

# 문제

 

# 문제 해설 및 코드 리뷰

이 문제는 무려 1솔만에 풀었습니다.

예제가 많아서 그런지 몰라도, 구현 문제 치고 원큐에 푼건 처음이라 내 자신이 자랑스러워서 기록에 남깁니다 ㅎ.

import java.util.*;
class Point{
	int z;
	int x;
	int y;
	int cost;
	Point(int z, int x, int y, int cost){
		this.z = z;
		this.x = x;
		this.y = y;
		this.cost = cost;
	}
}
class Main{
	static int[][][] arr = new int[5][5][5];
	static int[][][] map = new int[5][5][5];
	static boolean[][][] visit = new boolean[5][5][5];
	static boolean[] v = new boolean[5];
	static int[][] dir = {{-1 ,0, 0}, {1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};
	static int[] ans = new int[5];
	static int[] an = new int[5];
	static int[][][][] temp = new int[5][4][5][5];
	static int answer = Integer.MAX_VALUE;
	static Queue<Point> queue;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		for(int i = 0; i < 5; i++)
			for(int j = 0; j < 5; j++)
				for(int k = 0; k < 5; k++)
					arr[i][j][k] = scan.nextInt();
		scan.close();
        //미리 순서 + 회전바꿀 값들을 temp에 담음
		for(int index = 0; index < 5; index++) {
			for(int d = 0; d < 4; d++) {
				Queue<Integer> tt = new LinkedList<>();
                //d가 0일 땐 그대로
				if(d == 0) {
					for(int i = 0; i < 5; i++)
						for(int j = 0; j < 5; j++)
							temp[index][d][i][j] = arr[index][i][j];
				}else if(d == 1) { //시계방향 90도
					for(int i = 0; i < 5; i++)
						for(int j = 0; j < 5; j++)
							tt.offer(arr[index][i][j]);
					for(int i = 4; i >= 0; i--) 
						for(int j = 0; j < 5; j++)
							temp[index][d][j][i] = tt.poll();
				}else if(d == 2) { //180도회전
					for(int i = 0; i < 5; i++)
						for(int j = 0; j < 5; j++)
							tt.offer(arr[index][i][j]);
					for(int i = 4; i >= 0; i--)
						for(int j = 4; j >= 0; j--)
							temp[index][d][i][j] = tt.poll();
				}else {//시계방향 270도회전
					for(int i = 0; i < 5; i++)
						for(int j = 0; j < 5; j++)
							tt.offer(arr[index][i][j]);
					for(int i = 0; i < 5; i++)
						for(int j = 4; j >= 0; j--)
							temp[index][d][j][i] = tt.poll();
				}
			}
		}
		bruteForce(0);
		if(answer == Integer.MAX_VALUE)
			System.out.println(-1);
		else System.out.println(answer);
	}
	//회전(중복순열)
	static void bruteForce(int count) {
		if(count == 5) {
			backTracking(0);
			return;
		}
		for(int i = 0; i < 4; i++) {
			ans[count] = i;
			bruteForce(count + 1);
		}
	}
	//순서 바꾸기(순열)
	static void backTracking(int count) {
		if(count == 5) {
			bfs();
			return;
		}
		for(int i = 0; i < 5; i++) {
			if(!v[i]) {
				v[i] = true;
				an[count] = i;
				backTracking(count + 1);
				v[i] = false;
			}
		}
	}
    //map 새로 만들기
	static void bfs() {
		int index = 0;
		map = new int[5][5][5];
		while(index < 5) {
			int direction = ans[index];
			int tir = an[index];
			for(int i = 0; i < 5; i++)
				for(int j = 0; j < 5; j++)
					map[tir][i][j] = temp[index][direction][i][j];
			index++;
		}
		if(map[0][0][0] == 1)
			bfs2(0, 0);
		else if(map[0][0][4] == 1)
			bfs2(0, 4);
		else if(map[0][4][0] == 1)
			bfs2(4, 0);
		else if(map[0][4][4] == 1)
			bfs2(4, 4);
	}
	static void bfs2(int x, int y) {
		queue = new LinkedList<Point>();
		visit = new boolean[5][5][5];
		queue.offer(new Point(0, x, y, 0));
		visit[0][x][y] = true;
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			if(now.z == 4) {
				if(x == now.x || y == now.y)continue; 
                //꼭지점에 도달했을 때 최솟값 갱신
				if((now.x == 4 && now.y == 4) || (now.x == 4 && now.y == 0) || (now.x == 0 && now.y == 0) || (now.x == 0 && now.y == 4)) {
					answer = Math.min(answer, now.cost);
					break;
				}
			}
            //총 6가지 방향에 대해 탐색
			for(int i = 0; i < 6; i++) {
				int nz = now.z + dir[i][0];
				int nx = now.x + dir[i][1];
				int ny = now.y + dir[i][2];
				if(nz < 0 || nx < 0 || ny < 0 || nz >= 5 || nx >= 5 || ny >= 5)
					continue;
				if(visit[nz][nx][ny]) continue;
				if(map[nz][nx][ny] == 0) continue;
				queue.offer(new Point(nz, nx, ny, now.cost + 1));
				visit[nz][nx][ny] = true;
			}
		}
	}
}

사진만 봐도 아찔한 비주얼입니다.

푸는데 2시간 정도 걸린 것 같은데 이런 문제는 디버깅 한 번 하기 시작하면 답도 없어서 정확하게 푸는데 초점을 맞추었습니다.

문제를 요약하겠습니다.

# 문제 요약

1. 순서와 방향을 다 구하고 나서 3차원 배열을 구축하지 않고, 미리 경우의 수에 대한 arr값들을 한 차원 높은 배열에 저장한 뒤 배열을 새로 구할 때마다 값들을 꺼내와서 쓰기

2. temp배열을 [z][방향][x][y] 형태로 담고, 각각 회전했을 때와 순서를 여기에 담습니다. 자세한건 코드로 설명합니다.

3. 회전은 중복순열입니다. (1, 1, 1, 2, 2) 이 경우랑 (1, 1, 2, 2, 1) 이 경우랑 서로 다르죠?

4. 순서 바꾸는건 조합입니다. (1, 2, 3, 4, 5)와 (5, 4, 3, 2, 1)은 서로 다르며 (1, 1, 2, 3, 4) 같은건 나오면 안됩니다. (겹치는거x)

5. 이후부터는 3차원 BFS문제입니다.

코드를 봅시다.

여러분들이 제일 이해 안되고 ??? 싶은 로직이 제일 처음 등장합니다.

for(int index = 0; index < 5; index++) {
			for(int d = 0; d < 4; d++) {
				Queue<Integer> tt = new LinkedList<>();
				if(d == 0) {
					for(int i = 0; i < 5; i++)
						for(int j = 0; j < 5; j++)
							temp[index][d][i][j] = arr[index][i][j];
				}else if(d == 1) {
					for(int i = 0; i < 5; i++)
						for(int j = 0; j < 5; j++)
							tt.offer(arr[index][i][j]);
					for(int i = 4; i >= 0; i--) 
						for(int j = 0; j < 5; j++)
							temp[index][d][j][i] = tt.poll();
				}else if(d == 2) {
					for(int i = 0; i < 5; i++)
						for(int j = 0; j < 5; j++)
							tt.offer(arr[index][i][j]);
					for(int i = 4; i >= 0; i--)
						for(int j = 4; j >= 0; j--)
							temp[index][d][i][j] = tt.poll();
				}else {
					for(int i = 0; i < 5; i++)
						for(int j = 0; j < 5; j++)
							tt.offer(arr[index][i][j]);
					for(int i = 0; i < 5; i++)
						for(int j = 4; j >= 0; j--)
							temp[index][d][j][i] = tt.poll();
				}	
			}
		}

저는 배열을 회전할 때 queue를 쓰는 습관이 있어서 이렇게 나타내곤 하는데, d는 0일 때부터 시계방향으로 90도씩 회전한 결과입니다.

temp를 4차원을 쓴 이유는, temp의 첫 번째 차원은 "z차원"를 담을 것입니다. 무슨 말이냐면, 저희는 3차원의 bfs문제를 풀어야 합니다.

기존의 bfs방식과는 다르게 축이 한 가지 더 늘었기 때문에 x축, y축 말고도 하나의 축을 더 신경 써야 하는데요. 저 큐브모양의 정육면체의 각각의 층을 z축이라고 해본다면, 층마다 서로 다른 x,y값들이 존재해야 합니다.

이 z가 0 ~ 4까지 (1층 ~ 5층) 있기 때문에 하나의 층에서, 4가지 방향에 대해, x와 y의 값들을 넣을 수 있는 것입니다.

잘 생각해보세요. arr값들이 어떻게 저장될 수 있어야하는지

정리하자면, 하나의 층에 대해 90도씩 돌린 방향 총 4가지의 경우에 대한 x와 y의 회전을 담는다고 보면 되는 것입니다.

미리 이걸 만들어두고, 나중에 회전하고 순서를 바꾼 경우에 따라 그걸 그대로 차용하려는 의도입니다.

 

회전하는 경우의 수는 어떻게 구해야 할까요?

바로 백트래킹을 이용하여 구하셔야 합니다.

경우의 수를 구할 때에는 최고의 기법이지요.

//회전
	static void bruteForce(int count) {
		if(count == 5) {
			backTracking(0);
			return;
		}
		for(int i = 0; i < 4; i++) {
			ans[count] = i;
			bruteForce(count + 1);
		}
	}

ans라는 배열에, i들을 count인덱스마다 넣는데, 결과적으로 count가 5가 된다면 ans에는 전부 0이상의 값들이 채워지게 되고 이것이 재귀의 성질에 의해 return되면서 모든 경우의 수를 구할 수 있게 되는 것입니다.

회전의 경우는 visit배열이 필요 없기 때문에 중복되어도 되고 결과적으로 중복순열로직이 됩니다.

//순서 바꾸기
	static void backTracking(int count) {
		if(count == 5) {
			bfs();
			return;
		}
		for(int i = 0; i < 5; i++) {
			if(!v[i]) {
				v[i] = true;
				an[count] = i;
				backTracking(count + 1);
				v[i] = false;
			}
		}
	}

순서를 바꾸는 로직은 방문 체크가 필요하기 때문에 순열의 방식을 따릅니다.

그리고 여기에서는 an배열을 활용했는데요. 위의 로직과 아래의 로직 중 차이를 느끼실 수 있으시겠나요?

visit배열의 유무에 따라 만들어지는 경우의 수가 상이하게 달라진답니다.

그리고, 인덱스는 count마다 값을 넣어주었기 때문에 an배열 역시도 모든 인덱스가 0이상의 i값들로 채워지게 되고 이것이 재귀의 성질에 의해 return될 때마다 새로운 경우의 수를 만들게 되는 것입니다.

static void bfs() {
		int index = 0;
		map = new int[5][5][5];
		while(index < 5) {
			int direction = ans[index];
			int tir = an[index];
			for(int i = 0; i < 5; i++)
				for(int j = 0; j < 5; j++)
					map[tir][i][j] = temp[index][direction][i][j];
			index++;
		}
		if(map[0][0][0] == 1)
			bfs2(0, 0);
		else if(map[0][0][4] == 1)
			bfs2(0, 4);
		else if(map[0][4][0] == 1)
			bfs2(4, 0);
		else if(map[0][4][4] == 1)
			bfs2(4, 4);
	}

bfs에서는 본격적으로 너비 우선 탐색을 위한 map배열을 새롭게 만들어줍니다.

어짜피 5 x 5 x 5이기 때문에 위에서 temp만든거 상관없다 하실 수도 있겠지만 제 생각에는 재귀 문제에서 특히, queue라는 자료구조가 무한하게 생성되어 힙공간이 부족할 수 있기 때문에 일일히 회전한 값을 구해서 여기에서 사용하는것은 추천하지는 않습니다.

정답이 되는지는 모르겠다만 미리 구한걸 쓰는게 조금 더 메모리 공간은 줄일 수 있다고 생각합니다.

또한 문제 조건 중 주어진 것을 잘 살펴보면, 면을 공유하는 점에 도착하면 안되고 꼭지점에 도달해야 하므로 bfs2를 실행할 수 있는 조건을 여기에서 제어문을 통해 처리해주었습니다. 이제는 쉽습니다.

static void bfs2(int x, int y) {
		queue = new LinkedList<Point>();
		visit = new boolean[5][5][5];
		queue.offer(new Point(0, x, y, 0));
		visit[0][x][y] = true;
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			if(now.z == 4) {
				if(x == now.x || y == now.y)continue; 
				if((now.x == 4 && now.y == 4) || (now.x == 4 && now.y == 0) || (now.x == 0 && now.y == 0) || (now.x == 0 && now.y == 4)) {
					answer = Math.min(answer, now.cost);
					break;
				}
			}
			for(int i = 0; i < 6; i++) {
				int nz = now.z + dir[i][0];
				int nx = now.x + dir[i][1];
				int ny = now.y + dir[i][2];
				if(nz < 0 || nx < 0 || ny < 0 || nz >= 5 || nx >= 5 || ny >= 5)
					continue;
				if(visit[nz][nx][ny]) continue;
				if(map[nz][nx][ny] == 0) continue;
				queue.offer(new Point(nz, nx, ny, now.cost + 1));
				visit[nz][nx][ny] = true;
			}
		}
	}

queue와 visit을 새로 선언한 뒤 아까 구한 map을 이용하여 탐색을 시작합니다.

출발지점에서 꼭지점에 도달할 수 있는지 여부를 살펴야겠습니다.

꼭지점에 도달하려면 첫 번째로, z축의 값이 4가 되고, 출발지점과 면을 공유하면 안되므로 대각선 끄트머리 자리일 때에 도달했을 때만 정답으로 인정될 수 있습니다.

따라서 now.x와 now.y가 x나 y가 같을 때에는 값을 갱신하지 않고 이외의 경우에만 answer를 갱신합니다.

그리고 nz, nx, ny값을 구할 때 for문의 범위가 6인 것을 조심하셔야겠습니다.

 감사합니다.