[알고리즘 TIL] Q1890 (DFS+DP)

문제

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

트러블 슈팅

1. 중복 체크 없이 백트래킹 -> 시간초과

처음에는 단순히 백트래킹(DFS) 방식으로 (0, 0)부터 도착점 (N-1, N-1)까지 이동할 수 있는 모든 경로를 재귀적으로 탐색했다. 그런데 특정 좌표에 여러 경로로 도달할 수 있기 때문에, 같은 위치를 중복해서 수십, 수백 번 다시 탐색하게 되었고 결국 시간 초과가 발생했다.

 

2. 경로 누적 계산 없이 진행 → DP 도입 필요

백트래킹을 하면서 도착점까지 도달하는 경우를 발견하면 그때마다 count++ 식으로 경로를 세고 이미 도착한 좌표는 넘기려 했지만, 문제는 같은 위치에서 출발해 도착점까지 도달하는 경로 수를 고려하지 않고 있었다.

그래서 이 문제에 가장 적합한 방식은, (y, x) 좌표에서 도착점까지 갈 수 있는 경로 수를 dp[y][x]에 저장하고 재사용하는 방식이다. 이렇게 하면 이미 계산된 경로 수를 다시 구할 필요가 없어지고, 같은 위치에서 출발해 도착점까지 도달하는 경로 수도 고려된다. 또한, 시간 복잡도도 O(N²) 수준으로 최적화된다. (좌표마다 한 번씩만 방문함)

 

3. 0인 체스 좌표 고려 x

초기에는 점프 길이 0인 좌표에 대한 예외 처리를 하지 않았다. 하지만 도착점이 아닌 위치에서 점프가 0이면, 이동할 수 없으므로 재귀 호출이 자기 자신을 계속 호출하게 되어 무한 루프가 발생했다. 이는 곧 메모리 초과로 이어졌다.

 

따라서 아래와 같은 예외 처리가 반드시 필요하다:

if (chessBoard[y][x] == 0) return 0;

 

4. DP로 풀이
DFS 없이, 반복문만 사용하는 방법도 있다. 먼저, dp[y][x]를 (0,0)부터 (y,x)까지 도달할 수 있는 경로의 수라고 정의한다. 그 후 체스판을 이중 반복문으로 순회하며, 각 칸에 적힌 숫자만큼 아래쪽 또는 오른쪽으로 이동 가능한 다음 칸에 현재까지의 경로 수를 누적해준다.

그로 인해 순차적으로 DP 테이블을 채워나갈 수 있으며, 시간 복잡도는 O(N²) 로 매우 효율적이다.

long[][] dp = new long[N][N];
dp[0][0] = 1; 

for (int y = 0; y < N; y++) {
    for (int x = 0; x < N; x++) {
        if (dp[y][x] == 0 || board[y][x] == 0) continue; 

        int jump = board[y][x];

        if (y + jump < N) dp[y + jump][x] += dp[y][x]; 
        if (x + jump < N) dp[y][x + jump] += dp[y][x];
    }
}

코드

import java.io.*;

public class Q1890 {

    static int[][] chessBoard;
    static long[][] dp;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        chessBoard = new int[N][N];
        dp = new long[N][N];

        for (int i = 0; i < N; i++) {
            String[] inputStrArr = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                chessBoard[i][j] = Integer.parseInt(inputStrArr[j]);
            }
        }

        bw.write(dfs(0, 0) + "");
        bw.flush();
        bw.close();
        br.close();
    }

    // (y,x)에서 도착점까지 가는 모든 경로 수를 반환하는 함수
    private static long dfs(int y, int x) {
        if(y==N-1 && x==N-1) return 1;
        if(dp[y][x]>0) return dp[y][x];
        if (chessBoard[y][x] == 0) return 0;

        dp[y][x] = 0;

        int jump = chessBoard[y][x];

        if (y + jump < N) dp[y][x]+=dfs(y + jump, x);
        if (x + jump < N) dp[y][x]+=dfs(y, x + jump);

        return dp[y][x];
    }
}