[백준 17484번] 진우의 달 여행 (Small)

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

 

package bra;

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

public class Bra17484 {

    static int N;
    static int M;

    static int[][] arr;

    static int answer = 0;
    static int min = Integer.MAX_VALUE;

    static int[] dx = {1, 1, 1};
    static int[] dy = {-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());
            }
        }
        for (int i = 0; i < M; i++) {
            answer = arr[0][i];
            solution(0, 0, i, 3);
        }
        System.out.println(min);
    }

    static void solution(int level, int x, int y, int d) {
        if (level == N-1) {
            min = Math.min(answer, min);
            return;
        }

        for (int i = 0; i < 3; i++) {
            if(i==d){
                continue;
            }
            if (x + dx[i] >= 0 && x + dx[i] < N && y + dy[i] >= 0 && y + dy[i] < M) {
                answer += arr[x + dx[i]][y + dy[i]];
                solution(level + 1, x + dx[i], y + dy[i], i);
                answer -= arr[x + dx[i]][y + dy[i]];
            }

        }
    }
}

 

아 초반에 문제를 잘 못 읽어서 조금 해맸다... 처음 시작할때 3방향으로 갈 수 있는데 1방향으로 생각을 했다...

그리고 다다음 단계로 넘어가면 이전 방향이 해제가 되어야되는데 코드가 너무 복잡하게 풀었다. 사실 그냥 간단하게 d에다가 i 값을 넣어서 해결하면 될것을....

 

전형적인 dfs 구현문제다. 문제는 어렵지 않았다.