[백준] 11048. 이동하기

문제 링크

[백준] 11048. 이동하기

풀이 과정

입력이 최대 1000x1000의 크기를 가지므로, 메모이제이션을 활용해 문제를 풀어야 합니다.

평소 Top-down 방식의 재귀 함수 작성이 어려워서 Top-down과 Bottom-up 둘 다 사용해봤습니다.

Top-down 방식으로 작성하면서 시간초과를 많이 받았고, 평소 몰랐던 부분을 배울 수 있었습니다.

1. Scanner와 BufferedReader 는 혼용해서 사용하면 안된다. 처음부터 끝까지 하나의 입력 수단만 사용해야 한다.
2. Scanner 는 BufferedReader 보다 시간, 메모리상으로 확연한 차이를 보인다.
   • Scanner의 nextInt() 는 내부적으로 Integer 타입이 맞는지 패턴 검사를 하기 위해 스트링을 계속 만든다.
   • 반면, BufferedReader의 readLine() 은 StringBuffer에 문자들을 하나씩 append() 하는식으로 입력을 한 줄씩 완성시키고, 완성된 객체를 toString() 으로 문자열로 변환해준다.
   • 위의 과정들로 인해 메모리와 시간의 차이가 생긴다.
3. 문제 조건을 잘 읽고 메모이제이션 배열의 초기화를 잘 해줄 것. 사탕 개수가 0일 수 있으므로, 초기에 0으로 초기화하면 안됐다. -1로 바꾸고 성공.

Top-down

for (int[] arr : dp) Arrays.fill(arr, -1);

위에서 적은 것처럼, 경로상의 사탕의 개수가 0인 부분을, 다른 재귀에서 돌지 않도록 메모이제이션 배열을 -1로 초기화했습니다. 즉, 처음 방문하는 경로상 사탕의 총합 개수가 0개이면, 0개를 바로 리턴하도록 했습니다.

static int dfs(int x, int y) {
    if (dp[x][y] != -1) return dp[x][y];
    if (x == N - 1 && y == M - 1) return map[x][y];

    for (int d = 0; d < 3; d++) {
        int nx = x + dx[d], ny = y + dy[d];

        if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;

        dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + map[x][y]);
    }

    return dp[x][y];
}

탈출 조건은 다음과 같습니다.

• if (dp[x][y] != -1) return dp[x][y]; : 미리 구해둔 사탕 총합 개수가 있으면 그걸 리턴.
• if (x == N - 1 && y == M - 1) return map[x][y]; : 가장 오른쪽 방에서도 아래 for문을 돌지 않도록 바로 리턴.

Bottom-up

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1])) + map[i][j];
    }
}

미로 배열의 크기를 (N+1)x(M+1) 로 잡았습니다. 각 좌표에 대해 세 방향( ↘︎, →, ↓ ) 으로부터 올 수 있으므로, 최대값을 구하기 위해 반대( ↖︎, ←, ↑ ) 방향의 원소를 확인해봐야 합니다.

따라서, 만약 크기를 NxM으로 잡았다면 아래 사진과 같이 맨 윗줄, 맨 왼쪽 줄의 경우 각각 위, 왼쪽으로 배열의 범위를 벗어나게 되기 때문에 따로 확인을 위한 조건을 작성해줘야 하기 때문입니다.

또한, 배열을 0으로 초기화했기 때문에, 최대값을 비교하는 부분에서 전혀 문제되지 않습니다. 배열의 가로 및 세로 크기를 1씩 늘림으로써, 코드가 조금 깔끔해질 수 있었습니다.

코드

Top-down

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

public class Main {
    static int N, M;
    static int[][] map;
    static int[][] dp;
    static int[] dx = {1, 0, 1}, dy = {0, 1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        dp = new int[N][M];

        for (int[] arr : dp) Arrays.fill(arr, -1);

        System.out.println(dfs(0, 0));
    }

    static int dfs(int x, int y) {
        if (dp[x][y] != -1) return dp[x][y];
        if (x == N - 1 && y == M - 1) return map[x][y];

        for (int d = 0; d < 3; d++) {
            int nx = x + dx[d], ny = y + dy[d];

            if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;

            dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + map[x][y]);
        }

        return dp[x][y];
    }
}

Bottom-up

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

public class Main {
    static int N, M;
    static int[][] map;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N + 1][M + 1];
        dp = new int[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1])) + map[i][j];
            }
        }

        System.out.println(dp[N][M]);
    }
}