글 읽기 - 도저히 어떤부분이 잘못됐는지 모르겠습니다..

abcd1428 3년 전 0

미천한 알고리즘 실력때문에 매번 애를 먹네요..

아래의 소스가 어떤 부분이 잘못된 접근일지 감을 잡지 못하겠습니다.

이것저것 다 고쳐보면서 Long으로도 바꿔보고 질문 글보고 scanner도 써보고 했지만 찾지 못했습니다.

감사합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        y = Integer.parseInt(input[0]);
        x = Integer.parseInt(input[1]);

        data = new int[y][x];
        memo = new long[y][x];

        for(int i=0; i<y; i++) {
            String[] in = sc.nextLine().split(" ");
            for(int j=0; j<x; j++) {
                data[i][j] = Integer.parseInt(in[j]);
                memo[i][j] = -1;
            }
        }
        System.out.println(dfs(0,0)); //시작은 무조건 0,0
    }
    static int[][] data;
    static long[][] memo;
    static int[] ly = {-1, 0, 1, 0};//위 오 아 왼
    static int[] lx = {0, 1, 0, -1};
    static int y;
    static int x;

    static long dfs(int dy, int dx) {
        int me = data[dy][dx];
        if(dy == y-1 && dx == x-1) {
            return 1;
        } else {
            int total = 0;
            for(int i=0; i<4; i++) {
                int my = dy+ly[i];
                int mx = dx+lx[i];
                if(chk(my, mx)) {
                    if(memo[my][mx] > -1) {
                        total += memo[my][mx];
                        continue;
                    }
                    if(me > data[my][mx]) {
                        long d = dfs(my, mx);
                        total += d;
                        memo[my][mx] = d;
                    }
                }
            }
            return total;
        }
    }

    static boolean chk(int dy, int dx) {
        if(dy < 0 || dy >= y || dx < 0 || dx >= x) {
            return false;
        }
        return true;
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도저히 어떤부분이 잘못됐는지 모르겠습니다..

abcd1428 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말