BOJ 1937: 욕심쟁이 판다

문제 풀이

판다를 풀어놓는 시작점부터 판다가 이동하며 생존할 수 있는 최장 시간을 구하는 문제이다.
내가 생각한 아이디어는 다음과 같다.

• 판다를 풀어놓는 위치가 정해지지 않았으므로 for문을 통해 판다를 모든 위치에서 시작하는 경우의 수를 구한다.
• 생존할 수 있는 최장 시간을 구해야 하므로 해당 지점에서 이동할 수 있는 최장 기간을 저장해두고 이용한다.

어떤 순서로 문제를 풀었는지 살표보자.

• 대나무를 저장할 map, 해당 지점에서 판다가 생존할 수 있는 최장 일수를 저장하는 visit을 이용한다.
• 2중 for문을 통해 map을 전체 순회한다.

• 현재 위치인 curI, curJ에 이미 구한 최장 일수가 있다면 return해준다.
• curI, curJ에서 이동할 수 있는 nextI, nextJ를 구한다.
• 만약 nextI, nextJ의 대나무가 현재 curI, curJ의 대나무보다 많다면 이동할 수 있으므로 현재 visit에 저장된 수와 비교해서 max 값을 넣어준다.

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

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

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int answer = 1;
        int[][] visit = new int[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                answer = Math.max(answer, solution(visit, i, j));
            }
        }

        System.out.println(answer);
    }

    static int[] dirI = {0, 0, 1, -1};
    static int[] dirJ = {1, -1, 0, 0};
    static int solution(int[][] visit, int curI, int curJ) {
        if(visit[curI][curJ] != 0) {
            return visit[curI][curJ];
        }

        visit[curI][curJ] = 1;
        for(int index = 0; index < 4; index++) {
            int nextI = curI + dirI[index];
            int nextJ = curJ + dirJ[index];

            if(nextI >= N || nextI < 0 || nextJ >= N || nextJ < 0) {
                continue;
            }
            if(map[curI][curJ] < map[nextI][nextJ]) {
                visit[curI][curJ] = Math.max(visit[curI][curJ], solution(visit, nextI, nextJ) + 1);
            }
        }

        return visit[curI][curJ];
    }
}

github
백준