문제
우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.
[예시]
진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.
1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.
2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.
진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.
최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.
입력
첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다.
다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.
출력
달 여행에 필요한 최소 연료의 값을 출력한다.
예제 입력 1
6 4
5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58예제 출력 1
29풀이 및 해설
출력값: 진우가 달에 도달하기 위해 필요한 연료의 최솟값 구하기
[지구 → 달 이동조건]
1. 아래 방향으로만 이동 가능! 즉, 왼쪽 대각선 아래/아래/오른쪽 대각선 아래 세 가지 방향으로만 이동 가능
2. 전에 움직인 방향으로 연속해서 이동 불가능
[DFS로 풀이]
1. 0행에 있는 출발점 모두 DFS 수행
2. 각 DFS 수행할 때, 이전에 사용했던 방향을 제외한 방향으로만 DFS 수행(범위 벗어나지 않는 조건에서)
3. DFS 수행할 때, 연료 누적값 계산
4. N행에 도달한 경우 연료 최솟값 갱신
<시간복잡도 고려>
조건: 2≤ N, M ≤ 6 이므로,
- 0 행렬 수행(M번)
- DFS 시간 복잡도(이전 제외한 2가지 방향):
- 0행부터 N행까지이므로 N-1 - 따라서, 시간복잡도는 임
- 숫자 대입하면, 이므로 DFS로 수행해도 시간 초과 발생 X
Code
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [N, M] = input[0].split(' ').map(Number); // 행렬 크기
const space = []; // 지구와 달 사이 공간
for (let n = 1; n <= N; n++) space.push(input[n].split(' ').map(Number));
// 움직일 수 있는 방향
const directions = [
[1, -1], // 대각선 왼쪽 아래
[1, 0], // 아래
[1, 1], // 대각선 오른쪽 아래
];
let result = Number.MAX_SAFE_INTEGER;
const dfs = (r, c, direction, totalFuel) => {
// 달에 도착한 경우, 연료의 최솟값 갱신
if (r === N - 1) {
result = Math.min(result, totalFuel);
return;
}
for (let d = 0; d < 3; d++) {
// 이전 방향과 다른 방향으로만 이동
if (d !== direction) {
const [nextR, nextC] = [r + directions[d][0], c + directions[d][1]];
if (nextR >= 0 && nextR < N && nextC >= 0 && nextC < M) {
dfs(nextR, nextC, d, totalFuel + space[nextR][nextC]);
}
}
}
return;
};
for (let m = 0; m < M; m++) dfs(0, m, -1, space[0][m]);
console.log(result);DP로 풀어보기
3차원 배열 DP 만들기 → 왼쪽 대각선(0)/위(1)/오른쪽 대각선(2) 누적합
[초기값]
- 0 행은 모든 배열이 본인 연료 값임
DP[0][j][k] = space[0][j] - 위 왼쪽 대각선에서 오른쪽 아래 대각선 방향으로 올 수 없는 경우(=0열)
DP[i][0][2] = Infinity - 위 오른쪽 대각선에서 왼쪽 아래 대각선 방향으로 올 수 없는 경우(=M-1열)
DP[i][M-1][0] = Infinity
[점화식]
- 위 오른쪽 대각선에서 왼쪽아래 대각선 방향으로 이동
DP[i][j][0] = Min(DP[i-1][j+1][1], DP[i-1][j+1][2]) + space[i][j] - 위에서 바로 아래 방향으로 이동
DP[i][j][1] = Min(DP[i-1][j][0], DP[i-1][j][2]) + space[i][j] - 위 왼쪽 대각선에서 오른쪽 아래 대각선 방향으로 이동
DP[i][j][2] = Min(DP[i-1][j-1][0], DP[i-1][j-1][1]) + space[i][j]
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [N, M] = input[0].split(' ').map(Number); // 행렬 크기
const space = []; // 지구와 달 사이 공간
for (let n = 1; n <= N; n++) space.push(input[n].split(' ').map(Number));
// 움직일 수 있는 방향
const directions = [
[1, -1], // 대각선 왼쪽 아래
[1, 0], // 아래
[1, 1], // 대각선 오른쪽 아래
];
// 3차원 DP 배열 만들기(0: 왼쪽 대각선, 1: 위, 2: 오른쪽 대각선)
const dp = Array.from({ length: N }, () =>
Array.from({ length: M }, () => new Array(3).fill(Number.MAX_SAFE_INTEGER))
);
// 초기값 세팅
for (let m = 0; m < M; m++) {
// 1. 0 행은 모두 본인 값으로 초기화
for (let d = 0; d < 3; d++) dp[0][m][d] = space[0][m];
}
// 범위 벗어나는지 확인하는 함수
const isValid = (r, c) => {
return r >= 0 && r < N && c >= 0 && c < M;
};
for (let n = 1; n < N; n++) {
for (let m = 0; m < M; m++) {
// 위 오른쪽 대각선에서 들어올때(왼쪽 대각선 방향)
if (isValid(n - 1, m + 1))
dp[n][m][0] =
Math.min(dp[n - 1][m + 1][1], dp[n - 1][m + 1][2]) + space[n][m];
// 위에서 들어올때(아래 방향)
if (isValid(n - 1, m))
dp[n][m][1] = Math.min(dp[n - 1][m][0], dp[n - 1][m][2]) + space[n][m];
// 위 왼쪽 대각선에서 들어올때(오른쪽 대각선 방향)
if (isValid(n - 1, m - 1))
dp[n][m][2] =
Math.min(dp[n - 1][m - 1][0], dp[n - 1][m - 1][1]) + space[n][m];
}
}
let result = Number.MAX_SAFE_INTEGER;
for (let m = 0; m < M; m++) {
for (let d = 0; d < 3; d++) result = Math.min(result, ...dp[N - 1][m]);
}
console.log(result);