[BOJ] 5573

산책

5573번 https://www.acmicpc.net/problem/5573

분류

• Platinum 4

• 다이나믹 프로그래밍

해법

요즘 dp문제를 몇 개 풀어서 그런진 모르겠는데,
풀이가 바로 생각이 나서 너무 기분이 좋았습니다. 😆

dp[1][1]이 (1, 1) 교차로를 방문한 횟수라고 할 때,
산책은 아래 또는 오른쪽으로만 하고, 오늘과 내일 같은 교차로에서 같은 방향으로 가지 않으므로
dp[1][2]과 dp[2][1]을 알 수 있습니다.

이런 성질은 다른 모든 교차로에도 똑같이 적용되므로, 각 교차로의 방문 횟수를 알 수 있습니다.

우리가 원하는 것은 N번째 산책에서의 산책 종료지점이므로,
N - 1 번째 산책이 끝난 후 산책로의 상태가 필요합니다.

따라서, N - 1번째 산책이 끝났을 시점의 각 교차로 방문 횟수를 구합니다.
이 때 (i, j)번째 교차로의 방문 횟수가 홀수라면 산책 후에는 산책 전 (i, j)번째 교차로와 방향이 달라집니다.
만약 방문 횟수가 짝수라면 산책 후에는 산책 전 (i, j)번째 교차로와 방향이 같습니다.

이렇게 해서 N번째 산책을 시작하기 전 교차로의 상태를 업데이트해준 후,
dfs를 이용해서 산책 종료 지점을 탐색해주면 됩니다.

정답 코드

/*
BOJ 5573: 산책
*/

#include <bits/stdc++.h>
using namespace std;

int H, W, N;
int mat[1005][1005];
int dp[1005][1005]; // 각 칸에 들리는 횟수

void cnt() {
    dp[1][1] = N - 1; // N - 1 번째 산책을 마친 후에는 첫 칸에 들리는 횟수
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (mat[i][j] == 1) { // 원래 오른 쪽으로 가야 하는 칸이면
                dp[i][j + 1] += dp[i][j] / 2 + dp[i][j] % 2;
                dp[i + 1][j] += dp[i][j] / 2;
            }
            else { // 왼쪽으로 가야 하는 칸이면
                dp[i][j + 1] += dp[i][j] / 2;
                dp[i + 1][j] += dp[i][j] / 2 + dp[i][j] % 2;
            }
        }
    }
}

// cnt에서 세었을 때 짝수번 들린 칸이면 방향이 안바뀌고, 홀수번 들린 칸이면 방향이 바뀐다.
void update() {
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            mat[i][j] = dp[i][j] % 2 == 0 ? mat[i][j] : !mat[i][j];
        }
    }
}

void walk(int x, int y) {
    if (x > H || y > W) {
        cout << x << " " << y;
        return;
    }
    if (mat[x][y] == 0) walk(x + 1, y);
    else walk(x, y + 1);
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> H >> W >> N;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> mat[i][j];
        }
    }
    cnt();
    update();
    walk(1, 1);
    return 0;
}