[백준] 1890번. 점프(JAVA)

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

---

풀이

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][n];

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

        long[][] dp = new long[n][n];

        dp[0][0] = 1;

        Loop1:
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == n-1 && j == n-1){
                    break Loop1;
                }
                if(i + arr[i][j] >= 0 && i + arr[i][j] < n){
                    dp[i + arr[i][j]][j] += dp[i][j];
                }
                if(j + arr[i][j] >= 0 && j + arr[i][j] < n){
                    dp[i][j + arr[i][j]] += dp[i][j];
                }
            }


        }

        System.out.println(dp[n-1][n-1]);

    }
}

 

처음에 dfs로 풀었다가 꽤나 낭패를 본 문제이다.

 

이 계산이 맞을지는 모르겠지만 내 생각은 이러하다.

만약 dp로 풀었다면 모든 경우 2n^2의 계산이 들어간다. 한 칸당 두번씩 이동에 대한 검사를 해야하기 때문이다.

 

dfs라면? 문제에서 주어진 예시 상황에는 찰떡같이 작용하지만 이러한 상황을 생각해보자.

모든 칸이 1으로 되어있으나 마지막 0칸을 둘러싼 세칸은 2로 되어있는 것이다.

그럼 0,0에서 출발해서 (n-2, n-2)까지 모두 훑는다고 보면 된다. 이 때, (0,1) 에서 출발한 dfs 를 생각해보자. 이미 (1,0)과 매우 겹치게 (1,1) ~ (n-2, n-2)의 지점을 모두 훑게 된다. 즉, 한 번 안 된다!라고 알았음에도 불구하고 백트레킹이 적용되어 계속해서 탐색하게 된다는 것이다.

 

최근 문제를 풀다가 dfs로 풀면 안 되고 꼭 bfs로만 풀어야 하는 문제를 만났었다.(프로그래머스 게임 맵 최단거리)

알고리즘을 생각할 때 문제를 단순히 해결한다!도 중요할 수 있지만 최선인가? 라는 질문을 꼭 해봐야 100점으로 통과할 수 있을 것 같다.