[알고리즘 문제풀이] 백준 17484 진우의 달 여행 (완전탐색,DFS)

 

 

 

 

 

 

 

import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {

    static int N,M;

    static int[][] arr;

    static int ans;

    // 좌하단 , 하단 , 우하단
    // [y][x] (y,x)
    // beforeMove
    static int[] dy = {1,1,1};
    static int[] dx = {-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());
            }
        }

        ans=Integer.MAX_VALUE;

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

    static void dfs(int y,int x,int beforeWay,int sum){

/*
        if(y==N-1){
            ans=Math.min(ans,sum);
            return;
        }
*/

        for(int i=0;i<3;i++){
            if(beforeWay == i ) continue;
            int moveX = dx[i]+x;
            int moveY = dy[i]+y;

            if(moveY==N){
                ans=Math.min(ans,sum);
                return;
            }

            if(moveX<0 || moveY<0 || moveX>=M || moveY>N) continue;

            dfs(moveY,moveX,i,sum+arr[moveY][moveX]);



        }

    }

}