[자바] 백준 17848번: 진우와 달 여행(Small)

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

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

 

일단 문제를 봤을 때...

갈 수 있는 경로 중에서 최솟값만 찾아서 간다고 해도

결과는 최솟값이 나오지 않을 수 있다는 것을 알았다.

그래서 가능한 모든 경로를 봐야할 것이라 생각했고

백트래킹 알고리즘을 사용하면 될 것 같아 코드를 작성했다.

 

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

public class P17484 {

	static int n, m;
	static int[][] arr;
	static int result = Integer.MAX_VALUE, cost = 0;
	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());
			}
		}
		backtracking(0, 0, -99);
		System.out.println(result);

	}

	static void backtracking(int step, int before_x, int before_direction) {
		if (step == n) {
			// 완성
			if (cost < result)
				result = cost;

		} else if (step == 0) {
			// 첫시작
			for (int i = 0; i < m; i++) {

				cost += arr[0][i];
				backtracking(step + 1, i, -99);// 첫시작은 방향성이 없음
				cost -= arr[0][i];
			}
		} else {
			for (int i = 0; i < 3; i++) {
				if (dx[i] == before_direction)
					continue;// 같은방향 두번은 안됨

				int now = before_x + dx[i];
				if (now < 0 || now >= m)
					continue; // 벗어나는것 안됨

				cost += arr[step][now];
				backtracking(step + 1, now, dx[i]);
				cost -= arr[step][now];
			}
		}
	}

}