(브루트포스) BOJ 17474: 진우의 달 여행(Small)

BOJ 17474: 진우의 달 여행(Small)

import java.util.*;

public class BOJ_17484 {
	static int N, M;
	static int[][] map;
	static int answer = Integer.MAX_VALUE;
	static int[] deltaRow = { 1, 1, 1 };
	static int[] deltaCol = { -1, 0, 1 };

	public static void main(String[] args) {
		input();
		for (int i = 0; i < M; i++) {
			goToTheMoon(0, i, map[0][i], -1);
		}
		System.out.println(answer);
	}

	public static void input() {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}
	}

	public static void goToTheMoon(int row, int col, int total, int direction) {
		
		if (row == N - 1) {
			answer = Math.min(answer, total);
		}
		for (int i = 0; i < 3; i++) {
			int nextRow = row + deltaRow[i];
			int nextCol = col + deltaCol[i];

			if (nextCol < 0 || nextCol >= M || nextRow >= N) {
				continue;
			}
			if (direction == i) {
				continue;
			}

			if (total >= answer) {
				return;
			}

			goToTheMoon(nextRow, nextCol, total + map[nextRow][nextCol], i);

		}
	}
}