백준 17484번 : 진우의 달 여행 (Small) (자바)

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

---

문제

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

 

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

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

 

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

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

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

---

입력

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

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

---

출력

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

🔵풀이

처음에 dfs+백트래킹 조합으로 생각하였습니다. 그러나 진행방향이 아래로만 진행되기 때문에 백트래킹을 사용할 필요가 없었습니다. 단순히 x, y, 연료값, 이전 방향만 전달하며 dfs로 완전탐색하였습니다.

 

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

public class Main {
  static int N;
  static int M;
  static int[][] map;
  static int[] dx = {-1,0,1};
  static int[] dy = {1,1,1};
  static int min = Integer.MAX_VALUE;
  public static  void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
    N = Integer.valueOf(stringTokenizer.nextToken());
    M = Integer.valueOf(stringTokenizer.nextToken());
    map = new int[N][M];


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

    for (int i=0; i<M; i++){
      dfs(0,i,map[0][i], -1);
    }
    System.out.println(min);
  }
  static void dfs(int row, int column,int price, int direction){
    if (price>min){
      return;
    }
    if (row==N-1){
      min = price;
      return;
    }

    for (int i=0; i<3; i++){
      int nx = column+dx[i];
      int ny = row+dy[i];

      if (nx<0||ny<0||nx>M-1||ny>N-1||direction==i){
        continue;
      }
      dfs(ny,nx,price+map[ny][nx],i);
    }
  }
}