[Algorithm] 백준_진우의 달 여행 (Small)_17484번 (JAVA) 🌙

📝문제

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

우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.

진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.

1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.

2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.

진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.

최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.

입력

첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다.

다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.

출력

달 여행에 필요한 최소 연료의 값을 출력한다.

---

💡풀이

문제 유형

완전탐색

 

걸린 시간

18분

 

풀이 방법 도출

1. 행렬의 첫번째 행에 대해 전부 dfs 함수호출을 해주고
2. dfs 함수에서는 현재 방향을 매개변수로 받아 현재 방향과 다른 방향에 대해서만 다시 재귀호출 해주었다.
3. 이후 현재 열의 위치가 N-1이라면 현재까지의 합계를 min값과 비교한다.
4. 모든 재귀호출이 끝나면 min값을 출력해준다.

import java.util.*;
import java.io.*;
class Main{
    static int min = Integer.MAX_VALUE;
    static int N,M;
    static int[][] arr;
    static int[] dx = {1,1,1};
    static int[] dy = {-1,0,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < M; i++){
            dfs(0,i, -1, arr[0][i]);
        }

        System.out.println(min);
    }
    public static void dfs(int x, int y, int dir, int sum){
        if(x == N-1){
            min = Math.min(min, sum);
            return;
        }

        for(int i = 0; i < 3; i++){
            if(i != dir){
                int nx = x+dx[i];
                int ny = y+dy[i];

                if(nx < N && ny >= 0 && ny < M){
                    dfs(nx,ny,i,sum+arr[nx][ny]);
                }
            }
        }
    }
}

---

🤔Review

N,M의 최대 크기가 워낙 작아서 N, M (2≤ N, M ≤ 6)

바로 완전탐색으로 접근 할 수 있었다. 쉬웠다 이번 문제!