백준 1890 점프 (java) 시행착오과정 포함.

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

 

현재 칸에 쓰여진 수만큼 우측이나 하단으로 점프해가며 종착점까지 가는 경우의 수를 센다.

우측이나 하단으로 가므로 원래 위치로 돌아올 일은 없고, 총 경우의 수를 세기 때문에 visited 관리는 필요 X

(좌우상하 다 움직일 수 있었다면 어떻게 해야 했을까?)

1. bfs로 발 닿은 곳마다 방문 횟수를 늘려서 종착점 밟은 수를 모두 세 보자.

2. bfs하면서 나아간 곳의 방문횟수를 이번칸 방문횟수로 업데이트해보자. -> 이럼 종착점에 도달 못한 경우의 수도 합해서 세버리는 경우가 될 듯 한?

 

메모리초과로 틀린코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;

public class Main {
    static int n;
    static int[][] arr = new int[101][101];
    static long[][] steps = new long[101][101];
    static class point{
        public int row;
        public int col;
        public point(int row,int col){
            this.row=row;this.col=col;
        }
    }
        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            n=Integer.parseInt(br.readLine());
            for(int i=0;i<n;i++){
                String str = br.readLine();
                StringTokenizer token = new StringTokenizer(str);
                for(int j=0;j<n;j++){
                    arr[i][j]=Integer.parseInt(token.nextToken());
                }
            }

            ArrayDeque<point> dq = new ArrayDeque<>();
            dq.add(new point(0,0));
            int[] row ={0,1};
            int[] col ={1,0};
            while(!dq.isEmpty()){
                int len = dq.size();
                for(int i=0;i<len;i++){
                    point p = dq.poll();
                    steps[p.row][p.col]++;
                    if(arr[p.row][p.col]==0) continue;
                    for(int j=0;j<2;j++){
                        int drow=p.row+row[j]*arr[p.row][p.col];
                        int dcol=p.col+col[j]*arr[p.row][p.col];
                        if(drow>=0 && drow<n && dcol>=0 && dcol<n){
                            dq.add(new point(drow,dcol));
                        }
                    }
                }
            }
            System.out.println(steps[n-1][n-1]);
    }
}

굳이 bfs를 써야할까? 어차피 우하단으로만 가는데.

전체를 순회하면서 다음에 갈 수 있는 곳의 경우의수를 1씩 더해주자.

상하좌우를 모두 움직일 수 있었더라면 좌우나 위아래로 계속 쌓아주면서 무한까지 갔겠지만

여기선 되돌아갈일이 없잖아.

(DAG인 경우에서는 dp로 풀 수 있다. 효율적)

 

근데 그렇게 하면 도착점까진 한번에 갈 수 있지만 출발점에서 도달할 수 없는 포인트의 경우까지 추가되는데.

자신의 steps(방문횟수)가 0이면 스킵하도록 하자.

 

그렇게 구현하면 종착점 직전까지 가는 경로가 여러가지여도 한번만 추가될텐데.

자신의 steps 만큼 더해주도록 하자.