백준 10164번 격자상의 경로 [DP] :: 마이구미

이번 글은 백준 알고리즘 문제 10164번 "격자상의 경로" 를 다뤄본다.

동적계획법으로 접근하는 문제이다.

일단 문제를 보자.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.

동그라미 표시된 칸을 무조건 지나가는 경로의 수를 찾는 문제이다.

점화식을 만드는 방법은 문제에서 알려준 조건을 보면 쉽게 파악할 수 있다.

조건 1을 보면, 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다고 한다.

기준이 되는 칸으로 올 수 있는 경우는 해당 칸의 왼쪽칸과 윗칸이 된다.

위 그림을 활용하여 2차원 배열을 통해 점화식을 만들 수 있다.

dp[n][m] = dp[n][m-1] + dp[n-1][m]

왼쪽칸과 윗칸의 경우의 수를 더하면 현재 칸에 올 수 있는 경로를 구할 수 있다.

이 점화식을 통해 1에서 15까지의 모든 경로의 수를 구할 수 있다.

하지만 문제에서는 동그라미 표시를 생각해야하기 때문에 생각이 필요하다.

점화식을 만들때 고려했던 조건1을 생각해보면 쉽게 해결법을 찾을 수 있다.

오른쪽과 아래로만 이동이 가능하기 때문에 위와 같은 규칙을 볼 수 있다.

동그리마 표시를 기준으로 고려할 필요가 없는 칸들을 볼 수 있다.

dp[1][1] = 1;

for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= m; j++) {

        if (i == 1 && j == 1) {
            continue;
        }

        if ((i > r && j < c) || (i < r && j > c)) {
            dp[i][j] = 0;
        } else {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }

    }

}

주어지는 동그라미의 위치는 간단히 반복문을 통해서 구할 수 있다.

하지만 수학적으로 간단하게 생각하면 더욱 효율적으로 쉽게 구할 수 있다.

자세한 건 아래 Github URL을 참고하길 바란다.

백준 알고리즘 문제 10164번 격자상의 경로 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/dp/10164.java