[백준]BOJ 17484 진우의 달 여행 (Small) [자바/DFS]

문제자체는 간단합니다. 갈 수 있는 방향에 대해 가보고 달에 도착한다면 멈추고 최솟값을 갱신해 주는 완전탐색으로 풀 수 있습니다. 

 

 

다만, 삽질했던 점은 문제를 보면 시작 위치가 지구에서 출발한다는 것을 알 수 있습니다.

 즉, 지구 위치에서도 3방향으로 가볼 수 있다는 소리이므로, DFS 탐색을 수행할때 3방향 개수만큼 반복문을 돌려주며 모든 방향에 대해 탐색해보아야 합니다. 구현

for(int i = 0; i < M; i++) {
	for(int j = 0; j < 3; j++) {//처음에 시작할때 3방향으로 갈 수 있음
    		DFS 탐색 수행
     	}
 }

 

 

 

 

---

 

 

 

public class Main{

    private static int[][] maps;
    private static int M, N;
    private static int result;


    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());

        maps = new int[N][M];
        result = Integer.MAX_VALUE;

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

        for(int i = 0; i < M; i++) {
            for(int j = 0; j < 3; j++) {//처음에 시작할때 3방향으로 갈 수 있음
                solve(0, i, maps[0][i], j);
            }
        }

        System.out.println(result);
    }

    static int[][] dir = {{1, -1}, {1, 0}, {1, 1}};

    static void solve(int nowX, int nowY, int sum, int d) {
        if(nowX == N-1) {//도착한 경우
            result = Math.min(result, sum);
            return;
        }

        for(int i = 0; i < 3; i++) {
            if(i == d) continue;//같은 방향으로 두번 연속 움직임 x
            int nextX = nowX + dir[i][0];
            int nextY = nowY + dir[i][1];

            if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;

            solve(nextX, nextY, sum + maps[nextX][nextY], i);
        }

    }

}