[백준] BOJ - 17484 진우의 달 여행 (Small) 자바 java (실버3)

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

17484번: 진우의 달 여행 (Small)

 

1. 나의풀이

      

      

      

    
    

      <bash />
    
import java.util.*;
import java.io.*;
public class Main {
    static int n, m;
    static int[][] arr;
    static int[] visited;
    static int min= Integer.MAX_VALUE;
    static int[] ydir={-1,0,1};// 가능한 방향(왼아, 아, 오아)
    
    public static void main(String args[]) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        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());
                
            }    
        }
        
        //지구의 어느 곳에서든 출발할 수 있으므로 출발지점이 m개인 셈.
        for(int i=0;i<m;i++){
            visited=new int[n];//깊이는 n개
            visited[0]=i; // 방문한 y방향 인덱스 
            dfs(1, i, -1);
        }
        
        bw.write(String.valueOf(min));
        bw.flush();
        br.close();
        bw.close();
} 
    
    public static void dfs(int depth, int y, int dir){//이제 방문할 깊이, 현재 y인덱스, 이전에 이동한 방향 
        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]; //이동했을때 y 좌표 
            if(dy>=0 && dy<m && dir != i){//이동했을때 좌표를 벗어나지 않고 이전에 이동한 방향이 아닐때 
                visited[depth]=dy;//해당 깊이에 방문한 y방향 인덱스
                dfs(depth+1, dy, i);
                
            }
        }
    }
}