[백준 5573] 산책 - JAVA

문제 링크 : https://www.acmicpc.net/problem/5573

접근 방법

처음에 이 문제를 보고 이거는 시뮬레이션 문제 아니야? 라고 생각했었습니다.

그러나 무지막지한 $N$의 범위를 보고는 아니라는 것을 알았고 머리 속에서 시뮬레이션을 돌려봤습니다.

그러다 힌트를 얻게 됐는데
맨 위인 $(1, 1)$ 위치에서 $N$번 산책을 할 경우
오른쪽 또는 아래로 각각 $\frac{N}{2}$씩 흐르게 된다는 것을 알게 되었습니다.

$N$이 짝수인 경우와 홀수인 경우에 따라 달라지게 됩니다.

• 짝수: 오른쪽과 아래쪽 둘 다 $\frac{N}{2}$
• 홀수: 초기 설정된 방향으로 $\frac{N}{2}+1$, 반대는 $\frac{N}{2}$

즉 $dp$를 2중$for$문으로 순회하면서 아래와 오른쪽으로 산책하는 사람들을 전파한다면 $N$회의 시행에 대한 결과를 얻을 수 있다고 생각했습니다.

그런데 문제는 또 있었습니다

• $N$회에 대한 방문 횟수만 $dp$에 저장되고 그러면 마지막 방문은 어디로 했는지 어떻게 알지?
• $N$회 수행 후 각 교차로의 문자는 어떻게 바뀌어 있지?

첫 번째 문제 (마지막 방문 좌표 찾기)
첫 번째 문제에 대한 해결은 의외로 간단했습니다.

$dp$로 하고 싶은 것은 특정 횟수까지의 시행에 대한 생략이므로 $N$번째의 산책 경로를 알고 싶다면
$N-1$번째 까지의 산책까지만 기록하는 것입니다.

그리고 마지막 $N$번째 산책은 표지판 문자가 기록된 배열에 접근해 교차로에 적힌 문자대로 이동하면 됩니다.

두 번째 문제 (N회 시행 후 교차로 문자의 상태)
첫 번째 문제를 해결하면
$N$회 시행이 아니라
$N-1$회를 시행해야 한다는 것을 알게 되었을 겁니다.

그러나 달라지는건 없습니다.
중요한건 특정 교차로 $dp[i][j]$에 몇 번 방문하게 되느냐에 따라 시행 후의 교차로의 문자가 결정됩니다.

생각을 해보면 1회 방문하는 경우 초기 방향의 반대가 되고
2회 방문하는 경우 원상태로 돌아온다는 것을 알고 있습니다.

그렇기 때문에

• $dp[i][j]$의 방문 횟수가 짝수번이면 그대로
• $dp[i][j]$의 방문 횟수가 홀수번이면 반대로

변경해야 합니다.

이제 문자가 바뀐 교차로로 마지막 $N$번째 산책을 시행한다면 나가는 방향을 파악할 수 있고 문제를 해결하게 됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        boolean[][] isLeft = new boolean[H][W];

        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < W; j++) {
                if (Integer.parseInt(st.nextToken()) == 1) {
                    isLeft[i][j] = true;
                }
            }
        }

        int[][] dp = new int[H+1][W+1];
        dp[0][0] = N-1;

        int half;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                half = dp[i][j] / 2;

                dp[i][j+1] += half;
                dp[i+1][j] += half;

                if (dp[i][j] % 2 == 1) {
                    if (isLeft[i][j]) dp[i][j+1] += 1;
                    else dp[i+1][j] += 1;
                    isLeft[i][j] = !isLeft[i][j];
                }
            }
        }
        System.out.println(findRoute(isLeft, H, W));
    }

    static String findRoute(boolean[][] isLeft, int H, int W) {
        int y = 0;
        int x = 0;

        while (y < H && x < W) {
            if (isLeft[y][x]) x++;
            else y++;
        }

        return (y+1) + " " + (x+1);
    }
}

최적화 방법

아주 자잘한 최적화를 했습니다.
1과 0으로 들어오는 교차로 문자를
boolean[][] isLeft 라는 배열로 정의했습니다.

두 가지 방향밖에 없으니 메모리 최적화를 위해 boolean 타입을 사용했습니다.

커스텀 Read(Fast IO)를 구현한 1위를 제외하고는 비교적 메모리에 대한 최적화가 잘 된 것을 확인할 수 있습니다.