[JAVA] BOJ 백준 1937번 - 욕심쟁이 판다

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

---

2. 내가 푼 방법

DP문제이다. 현재 위치에서 이동할 수 있는 칸의 수를 카운팅한 적이 없다면 sum 함수를 돌면 된다.

 

Integer 형인 이차원 배열을 사용하여 이전에 방문한 적이 없는 null일 경우, 상하좌우로 이동할 수 있는 더 큰 값이 있다면 그 칸들 중 최대 칸 이동 + 1을 해주고, 없다면 그냥 1이 된다.

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1937.java

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int[][] arr;
    static Integer[][] move;
    static int result;

    public static void main(String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (move[i][j] != null) continue;
                sum(i, j);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                result = Math.max(result, move[i][j]);
            }
        }
    }

    public static void sum(int i, int j) {
        move[i][j] = 1;

        if (i-1 >= 0 && arr[i-1][j] > arr[i][j]) {
            if (move[i-1][j] == null) sum(i-1, j);
            move[i][j] = Math.max(move[i][j], move[i-1][j] + 1);
        }
        if (i+1 < N && arr[i+1][j] > arr[i][j]) {
            if (move[i+1][j] == null) sum(i+1, j);
            move[i][j] = Math.max(move[i][j], move[i+1][j] + 1);
        }
        if (j-1 >= 0 && arr[i][j-1] > arr[i][j]) {
            if (move[i][j-1] == null) sum(i, j-1);
            move[i][j] = Math.max(move[i][j], move[i][j-1] + 1);
        }
        if (j+1 < N && arr[i][j+1] > arr[i][j]) {
            if (move[i][j+1] == null) sum(i, j+1);
            move[i][j] = Math.max(move[i][j], move[i][j+1] + 1);
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

비슷한 유형의 문제를 풀어본 적이 있어서 금방 풀어낼 수 있었다.

더 열씨미 머릿속에 차곡차곡,,, 쌓아나가자,,