🔎

답안

1. 문제 파악 2. 풀이

1. 문제 파악

파이에서 썬으로 가는 최단거리를 구하고, 최단경로를 행렬의 좌표값으로 출력해야 합니다. 이때, 큐브 형태임을 주의해야 합니다.

난이도가 어려운 만큼 신입 입사 문제로 나올 확률은 낮지만, 이차원 맵에서의 최단 경로를 구하는 문제는 종종 출제되기 때문에 잘 알아두면 좋습니다.

풀이는 맵의 크기를 줄여서 진행하고, 2사분면과 4사분면만을 풀이하겠습니다. 나머지는 6번의 회전 문제와 함께 고려해서 풀어보세요.

2. 풀이

3차원 배열을 이차원 배열로 바꿔줍니다. 이때, 3차원 배열과 폭은 같지만 높이는 2배가 된다는 점을 주의해야 합니다.

최단 거리와 최단 경로를 구해야 하는 게 목적이기 때문에, 가중치의 값을 저장하는 변수와 좌표를 저장할 수 있는 배열을 정의합니다.

상단의 오른쪽에 위치한 8에서 맨 아래의 왼쪽에 위치한 8까지 이동해야 합니다. 시작점을 99, 99로 절대 나올 수 없는 값으로 초기화해서 시작점까지의 경로를 거슬러 올라갈 수 있도록 합니다.

최단 거리를 구하기 위해서는 가중치의 값이 작은 값을 선택해서 움직여야 합니다. 따라서 이차원 배열의 맨 위쪽, 맨 오른쪽, 그리고 가운데 부분을 나눠서 생각해 봐야 합니다. 또한, 경로를 구하기 위해서 배열에 좌표를 저장합니다.

무한 반복문을 돌려 좌표 값을 출력합니다. 이때, 시작점의 좌표 값을 99, 99로 초기화했기 때문에 x 값을 의미하는 i와 y 값을 의미하는 j가 99, 99일 때 좌표 값을 모두 출력한 것이기 때문에 break합니다.

이제 모든 탐색이 끝났기 때문에 좌표저장배열을 이용해 최단 경로를 구해야 합니다. k를 정의해서 k가 0일 때 cross 배열의 가장 아랫 부분의 왼쪽으로 초기화합니다. 즉, 탐색의 끝부분이 시작 부분이 되도록 합니다.

k가 0이 아니라면 좌표저장배열에 있던 값을 가지고 와서 출력합니다. 또한 k 값을 1만큼 증가시켜 7번의 조건문을 만족시킵니다.


public class Q7 {
	public static void main(String[] args) {
		int[][][] cross = {
				{ 
					{ 3, 0, 1, 1, 8 }, 
					{ 5, 0, 4, 5, 4 }, 
					{ 1, 5, 0, 5, 1 }, 
					{ 1, 2, 1, 0, 1 }, 
					{ 0, 2, 5, 1, 1 } 
				},
				{ 
					{ 1, 2, 0, 3, 3 }, 
					{ 1, 2, 0, 2, 4 }, 
					{ 1, 2, 0, 2, 4 }, 
					{ 4, 2, 0, 0, 1 }, 
					{ 8, 4, 1, 1, 0 } 
				} 
		};

		solution(cross);
	}

	public static void solution(int[][][] cross) {
		int[][] cross_ = new int[cross[0].length * 2][cross[0][0].length];

		for (int i = 0; i < cross_.length; i++) {
			for (int j = 0; j < cross_[0].length; j++) {
				if (i < cross[0].length) {
					cross_[i][j] = cross[0][i][j];
				} else {
					cross_[i][j] = cross[1][i - cross[0].length][j];
				}
			}
		}

		int[][] 가중치누적값 = new int[cross_.length][cross_[0].length];
		int[][][] 좌표저장 = new int[cross_.length][cross_[0].length][2];

		for (int i = 0; i < cross_.length; i++) {
			for (int j = 0; j < cross_[0].length; j++) {
				if (i == 0 && j == 4) {
					가중치누적값[i][j] = cross_[i][j];
					좌표저장[i][j] = new int[] { 99, 99 };
				} else if (i == 0) {
					가중치누적값[i][j] = 가중치누적값[i][j + 1] + cross_[i][j];
					좌표저장[i][j] = new int[] { i, j + 1 };
				} else if (j == 4) {
					가중치누적값[i][j] = 가중치누적값[i - 1][j] + cross_[i][j];
					좌표저장[i][j] = new int[] { i - 1, j };
				} else {
					if (가중치누적값[i][j + 1] > 가중치누적값[i - 1][j]) {
						가중치누적값[i][j] = 가중치누적값[i - 1][j] + cross_[i][j];
						좌표저장[i][j] = new int[] { i - 1, j };
					} else {
						가중치누적값[i][j] = 가중치누적값[i][j + 1] + cross_[i][j];
						좌표저장[i][j] = new int[] { i, j + 1 };
					}
				}
			}
		}

		int i = 0, j = 0, k = 0;
		while (true) {
			if (i == 99 || j == 99) {
				break;
			}

			if (k == 0) {
				i = 좌표저장[cross_.length - 1][0][0];
				j = 좌표저장[cross_.length - 1][0][1];
			} else {
				i = 좌표저장[i][j][0];
				j = 좌표저장[i][j][1];
			}

			System.out.println(i + " " + j);
			k++;
		}

		// 여기까지 2사분면과 4사분면을 살펴봤습니다.
		// 나머지 부분은 6번 문제의 회전과 함께 고려해 보면 풀 수 있습니다.
	}
}


int[][] cross_ = new int[cross[0].length * 2][cross[0][0].length];

for (int i = 0; i < cross_.length; i++) {
		for (int j = 0; j < cross_[0].length; j++) {
				if (i < cross[0].length) {
					cross_[i][j] = cross[0][i][j];
				} 
				else {
					cross_[i][j] = cross[1][i - cross[0].length][j];
				}
		}
}


int[][] 가중치누적값 = new int[cross_.length][cross_[0].length];
int[][][] 좌표저장 = new int[cross_.length][cross_[0].length][2];


if (i == 0 && j == 4) {
		가중치누적값[i][j] = cross_[i][j];
		좌표저장[i][j] = new int[] { 99, 99 };
}


else if (i == 0) {
					가중치누적값[i][j] = 가중치누적값[i][j + 1] + cross_[i][j];
					좌표저장[i][j] = new int[] { i, j + 1 };
} else if (j == 4) {
					가중치누적값[i][j] = 가중치누적값[i - 1][j] + cross_[i][j];
					좌표저장[i][j] = new int[] { i - 1, j };
} else {
				if (가중치누적값[i][j + 1] > 가중치누적값[i - 1][j]) {
					가중치누적값[i][j] = 가중치누적값[i - 1][j] + cross_[i][j];
					좌표저장[i][j] = new int[] { i - 1, j };
				}
				else {
					가중치누적값[i][j] = 가중치누적값[i][j + 1] + cross_[i][j];
					좌표저장[i][j] = new int[] { i, j + 1 };
				}
}


if (i == 99 || j == 99) {
		break;
}


if (k == 0) {
		i = 좌표저장[cross_.length - 1][0][0];
		j = 좌표저장[cross_.length - 1][0][1];
}


else {
		i = 좌표저장[i][j][0];
		j = 좌표저장[i][j][1];
}

System.out.println(i + " " + j);
k++;