백준 17484

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

---

문제

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

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

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

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

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

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

---

입력

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

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

---

출력

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

---

제한

• 시간 제한 : 1초
• 메모리 제한 : 256MB

---

문제 풀이 과정

dfs, 완전 탐색으로 해결 가능하다.

모두 비교해보면서, 방향만 체크하면 된다.

---

정답 코드

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

class Main17484 {

	private static final int[] dy = {-1, 0, 1};
	private static int N, M, ans;
	private static int[][] map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		ans = Integer.MAX_VALUE;

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

		for (int i = 0; i < M; i++) { //모든곳에서 출발
			dfs(1, i, -1, map[0][i]);
		}

		System.out.println(ans);
	}

	private static void dfs(int depth, int y, int dir, int current) {
		if (depth == N) { //마지막 줄이라면
			ans = Math.min(ans, current); //최소 연료 값 비교
			return;
		}

		for (int i = 0; i < 3; i++) {
			int ny = y + dy[i];

			if (ny < 0 || ny >= M) {
				continue;
			}

			if (dir != i) { //현재 위치로 온 방법이 전의 방법이랑 같지 않아야 한다.
				dfs(depth + 1, ny, i, current + map[depth][ny]);
			}
		}
	}

}