[백준 온라인 저지(BOJ)] 17484번 진우의 달 여행(small) (dfs 문제)

BOJ 17484번 진우의 달 여행(Small) 자바(java) 풀이

• 랭크 : 실버5
• 백준 온라인 저지(BOJ) 17484번 진우의 달 여행(Small) 문제 자바 풀이
• 백준 17484번 진우의 달 여행(Small)
  
  
  

문제 정리

1. 지구와 우주 사이는 NxM 행렬로 나타낼 수 있다.
2. 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.
3. 지구->달로 가는 경우 왼쪽 아래, 아래, 오른쪽 아래 3가지의 방향으로만 이동 가능하다.
4. 같은 방향으로 두번 연속 움직일 수 없다.
5. 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙해야한다.

• 달에 도달하기 위해 필요한 연료의 최소값을 계산하자.
  
  
  

문제 풀이

이 문제는 dfs 함수만 구현할 수 있으면 풀 수 있는 문제입니다.

1. 입력을 받아 2차원 배열에 저장합니다.
2. 지구의 어느 위치에서 시작하든 상관이 없기 때문에 시작 위치를 다르게 하며 0행의 모든 열에서 dfs를 통해 탐색합니다.
3. dfs의 인자로 depth를 주어 마지막 줄에 도달했음을 인식하고, dir을 주어 이 전에 어느 방향으로 이동했는지의 정보를 기억합니다.
4. 배열의 범위를 넘지 않는지와 이전의 방향과 같지 않은지를 체크 하며 탐색합니다.
5. 행의 어느 열을 방문했는지의 정보를 visited에 저장합니다. 이 정보를 가지고 마지막 행에 도달했을때 소모한 연료의 양을 계산할 수 있습니다.
6. 소모한 연료의 양을 계산하여 min값보다 작다면 갱신해줍니다.
   
   
   

진우의 달 여행 small 자바 코드

자바 코드 github

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

class Main{    
    static int n,m;
    static int arr[][];
    static int min = Integer.MAX_VALUE;
    // -1: 왼쪽 아래
    // 0: 아래
    // 1: 오른쪽 아래 방향
    static int[] ydir = {-1, 0, 1};
    static int[] visited;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 전에 움직인 방향으로 움직일 수 없다.

        String[] temp = br.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        arr = new int[n][m];

        for(int i=0; i<n; i++) {
            String[] temp2 = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                arr[i][j] = Integer.parseInt(temp2[j]);
            }
        }

        for(int i=0; i<m; i++) {
            visited = new int[n];
            visited[0] = i;
            dfs(1, i, -1);
        }

        bw.write("" + min);
        bw.flush();
        bw.close();
        br.close();
    }

    // 완탐해야함
    public static void dfs(int depth, int y, int dir) {
        if(depth == n) {
            int sum = arr[0][visited[0]];
            for(int i=1; i<n; i++) {
                sum += arr[i][visited[i]];
            }

            min = min > sum ? sum : min;
            return;
        }

        // 전에 이동했던 방향인지도 고려!
        for(int i=0; i<3; i++) {
            int dy = y + ydir[i];
            if(isValidPosition(dy) && dir != i) {
                visited[depth] = dy;
                dfs(depth+1, dy, i);
            }
        }
    }

    public static boolean isValidPosition(int y) {
        if(y < 0 || y >= m)
            return false;
        return true;
    }
}