글 읽기 - 어디서 문제가 있을까요?

snowoo0 2년 전 0

구글링 해보니까 DP로 푸는 솔루션이 많던데 DP까지는 생각을 못했고

단순히 이 경로로 와서 이전에 목표에 도착할 수 있었으면 가고, 불가능 했으면 탐색하지 않는다. 라는 생각으로 구현한 코든데 어디서 문제가 되는지 모르겠습니다.

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

public class Main {

    static int[][] height;
    static int[][] node;  // 첫 방문 0, 목표 도착 가능 1, 목표 도착 불가능 -1 
    static int n, m;
    static int[][] dir = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int result = 0;

    static int backTracking(int r, int c) {

        if(r == n - 1 && c == m - 1) {
            result++;
            return 1; // 도착 가능한 경우 1을 반환 
        }

        int h = height[r][c];

        for (int i = 0; i < 4; i++) {
            int nextR = r + dir[i][0];
            int nextC = c + dir[i][1];
            if (nextR >= 0 && nextR < n && nextC >= 0 && nextC < m && height[nextR][nextC] < h
                && node[nextR][nextC] != -1) {
                node[r][c] = backTracking(nextR, nextC);
            }
        }
        
        // 이미 다른 곳을 도착할 수 있었으면 1 상태를 유지. 그 외에는 도착 불가능한 경우니 -1  
        return node[r][c] = node[r][c] != 1? -1 : 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());
        height = new int[n][m];
        node = new int[n][m];

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

        node[n-1][m-1] = 1;
        backTracking(0, 0);
        for (int i = 0; i < n; i++) System.out.println(Arrays.toString(node[i]));
        System.out.println(result);
        br.close();

    }
}

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

문제

문제

출처

ICPC

어디서 문제가 있을까요?

snowoo0 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말