Rook Path( Atcoder 232-E )

문제 : https://atcoder.jp/contests/abc232/tasks/abc232_e

E - Rook Path

 

문제 파악하기

(x1, y1)에 위치한 룩(Rook)을 K번 움직여서 (x2, y2)에 도달하게 만드는 방법의 수를 구하는 문제입니다. 룩은 현재 위치에서 가로/세로 방향으로 어디든 갈 수 있으며, 주어지는 체스판의 넓이(10⁹*10⁹)와 움직일 수 있는 횟수(10⁶)을 본다면 완전탐색을 통해 모든 경우의 수를 구하기는 힘들다는 걸 알 수 있습니다. 그럼 어떻게 모든 방법의 수를 구할 수 있을까요? 이는 문제의 관점을 바꿔보면 해결할 수 있습니다.

 

문제 해결하기

우리는 지금 룩이 갈 수 있는 각각의 위치에 대해 생각하기에 문제가 상당히 어렵게 느껴집니다. 각각의 위치를 바라보는 대신, 문제를 상태의 관점에서 바라보면 문제가 간단해집니다. 현재 룩의 위치와 목표 위치(x2, y2)를 비교해봅시다. 룩은 항상 체스판 속 (a, b)의 위치에 있습니다. 그리고 (a, b)의 위치는 우리가 원하는 결괏값 (x2, y2)와 비교할 수 있습니다. (a, b)와 (x2, y2)를 비교하면 항상 다음 4가지 경우 중 1가지 경우에 포함됩니다.

(1) a != x2 and b != y2

(2) a != x2 and b == y2

(3) a == x2 and b != y2

(4) a == x2 and b == y2

 

그렇다면 우리는 룩이 어떤 상태에 있든 4가지 중 1가지 경우에 포함되며, 현재 룩의 상태는 다음 룩의 상태에 영향을 미친다는 걸 알 수 있습니다. 따라서 우리는 이전 룩의 상태를 만들 수 있는 경우의 수를 참고하여 현재 룩의 상태를 만들 수 있는 경우의 수를 차례대로 구한다면 문제를 풀 수 있습니다. 예를 들어 현재 (2)의 상태에 해당하는 경우의 수를 구하고 싶다고 가정해보겠습니다. (2)의 상태는 목표 위치와 y값만 같은 상태입니다. (2)의 상태를 만들 수 있는 이전 상태는 총 3가지입니다. 첫 번째, 이전 (1)의 상태에서 y값을 y2로 이동하는 경우입니다. 두 번째, 이전 (2)의 상태에서 현재 x값의 위치와 x2의 위치를 제외한 x값으로 이동하는 경우입니다.  세 번째, 이전 (4)의 상태에서 다른 x값으로 이동하는 경우입니다. 이 3가지를 점화식으로 표현하면 다음과 같이 표현할 수 있습니다.

dp[idx][2] = dp[idx-1][1] + dp[idx-1][2]*(H-2) + dp[idx-1][4]*(H-1)

 

이렇게 (1)~(4)의 상태는 위와 같이 점화식을 통해 구할 수 있습니다. 그리고 룩은 K번의 이동을 한다고 했기 때문에 우리가 원하는 결괏값은 dp[K][4]에 저장될 것입니다.

 

소스코드

#include <stdio.h>
#include <utility>
#define NMAX 1000010
#define MOD 998244353
#define lint long long int
#define PAIR pair<lint, lint>
using namespace std;
 
lint H, W, K;
PAIR p1, p2;
 
lint dp[NMAX][4];
 
int main() {
    // input
    scanf("%lld %lld %lld", &H, &W, &K);
    scanf("%lld %lld %lld %lld", &p1.first, &p1.second, &p2.first, &p2.second);
 
    // init
    if(p1 == p2) dp[0][3] = 1;
    else if(p1.first == p2.first) dp[0][2] = 1;
    else if(p1.second == p2.second) dp[0][1] = 1;
    else dp[0][0] = 1;
 
    // dp[i][0]: 모두 다른 경우 / dp[i][1]: y좌표가 같은 경우
    // dp[i][2]: x좌표가 같은 경우 / dp[i][3]: (x, y)좌표 모두 같은 경우
    for(int i=1;i<=K;i++) {
        dp[i][0] = ( dp[i-1][0]*(W+H-4)%MOD + dp[i-1][1]*(W-1)%MOD + dp[i- 1][2]*(H-1)%MOD )%MOD;
        dp[i][1] = ( dp[i-1][0] + dp[i-1][1]*(H-2)%MOD + dp[i-1][3]*(H-1)%MOD )%MOD;
        dp[i][2] = ( dp[i-1][0] + dp[i-1][2]*(W-2)%MOD + dp[i-1][3]*(W-1)%MOD )%MOD;
        dp[i][3] = ( dp[i-1][1] + dp[i-1][2] )%MOD;
    }
 
    printf("%lld", dp[K][3]);
}

후기

문제를 순진하게 읽는다면 어렵게 느껴질 문제입니다. DP문제답게 추상화 과정이 핵심인 문제입니다. 오랜만에 재미있는 문제였습니다. 동적 프로그래밍을 연습하는 사람이나 좋아하는 사람에게 꼭 추천하고 싶은 문제입니다.