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번 문제의 회전과 함께 고려해 보면 풀 수 있습니다.
}
}
1. 문제 파악
- 파이에서 썬으로 가는 최단거리를 구하고, 최단경로를 행렬의 좌표값으로 출력해야 합니다. 이때, 큐브 형태임을 주의해야 합니다.
- 난이도가 어려운 만큼 신입 입사 문제로 나올 확률은 낮지만, 이차원 맵에서의 최단 경로를 구하는 문제는 종종 출제되기 때문에 잘 알아두면 좋습니다.
- 풀이는 맵의 크기를 줄여서 진행하고, 2사분면과 4사분면만을 풀이하겠습니다. 나머지는 6번의 회전 문제와 함께 고려해서 풀어보세요.
2. 풀이
- 3차원 배열을 이차원 배열로 바꿔줍니다. 이때, 3차원 배열과 폭은 같지만 높이는 2배가 된다는 점을 주의해야 합니다.
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];
- 상단의 오른쪽에 위치한 8에서 맨 아래의 왼쪽에 위치한 8까지 이동해야 합니다. 시작점을 99, 99로 절대 나올 수 없는 값으로 초기화해서 시작점까지의 경로를 거슬러 올라갈 수 있도록 합니다.
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 };
}
}
- 무한 반복문을 돌려 좌표 값을 출력합니다. 이때, 시작점의 좌표 값을 99, 99로 초기화했기 때문에 x 값을 의미하는 i와 y 값을 의미하는 j가 99, 99일 때 좌표 값을 모두 출력한 것이기 때문에 break합니다.
if (i == 99 || j == 99) {
break;
}
- 이제 모든 탐색이 끝났기 때문에 좌표저장배열을 이용해 최단 경로를 구해야 합니다. k를 정의해서 k가 0일 때 cross 배열의 가장 아랫 부분의 왼쪽으로 초기화합니다. 즉, 탐색의 끝부분이 시작 부분이 되도록 합니다.
if (k == 0) {
i = 좌표저장[cross_.length - 1][0][0];
j = 좌표저장[cross_.length - 1][0][1];
}
- k가 0이 아니라면 좌표저장배열에 있던 값을 가지고 와서 출력합니다. 또한 k 값을 1만큼 증가시켜 7번의 조건문을 만족시킵니다.
else {
i = 좌표저장[i][j][0];
j = 좌표저장[i][j][1];
}
System.out.println(i + " " + j);
k++;