[완전탐색] 백준 17484 진우의 달 여행 JAVA

package com.test.exhaustiveSearch;

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

public class ES_6_17484 {
    static int[][] board;
    static int x;
    static int y;
    static int minFuel = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        // [완전탐색] 백준 17484 진우의 달 여행 JAVA
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        y = Integer.parseInt(input[0]);
        x = Integer.parseInt(input[1]);

        board = new int[x][y];
        for (int i = 0; i < y; i++) {
            String[] row = br.readLine().split(" ");
            for (int j = 0; j < x; j++) {
                board[j][i] = Integer.parseInt(row[j]);
            }
        }

        for (int i = 0; i < x; i++) {
            explorePath(i, 0, 0, -1);
        }

        System.out.println(minFuel);
    }

    private static void explorePath(int curX, int curY, int totalFuel, int prevDirection) {
        if (curY == y) {
            minFuel = Math.min(minFuel, totalFuel);
            return;
        }

        int[] dx = {-1, 0, 1};

        for (int i = 0; i < 3; i++) {
            int nextX = curX + dx[i];
            if (nextX < 0 || nextX >= x || i == prevDirection) continue;

            int nextFuel = totalFuel + board[nextX][curY];
            explorePath(nextX, curY + 1, nextFuel, i);
        }
    }
}

 

시간복잡도 : O(3^y * x)