DP :: 백준 :: 욕심쟁이 판다 :: 1937

욕심쟁이 판다 1937

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

map[][]에 대나무 숲 정보를 다 집어넣고 map[1][1]부터 dfs로 이동 가능한 곳 모두 탐색한 뒤 최댓값 출력하면 될것같은데...

알고리즘 공부하던 초창기에 푼거라 빙빙 돌아간 것 같다..

어쨋든, 코드를 설명하자면

  1. bamboo[][] 배열에 입력받은 정보들을 집어넣는 동시에 ArrayList<Node> al에도 집어넣는다.

  2. al을 대나무 양을 기준으로 sort 한다.

  3. al에 들어있는 정보들을 하나씩 get 해와서 탐색한다.

  4. 탐색 종료 후 최댓값을 찾아서 출력한다.

이렇게 된다...

예전에 풀었던 문제를 다시 보니 뭔가 실력이 향상된것 같아 뿌듯하다. 

물론 코딩테스트는 다 떨어졌지만..ㅠ__ㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
  
public class Main {
    static int[][] bamboo;
    static int[][] index;
    static int[][] route;
    static ArrayList<Node> al;
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        bamboo = new int[n + 1][n + 1];
        route = new int[n + 1][n + 1];
        String[] tmp;
        int l;
        al = new ArrayList<>();
        for (int r = 1; r <= n; r++) {
            tmp = br.readLine().split(" ");
            for (int c = 1; c <= n; c++) {
                l = Integer.parseInt(tmp[c - 1]);
                al.add(new Node(l, r, c));
                bamboo[r][c] = l;
            }
        }
        Collections.sort(al);
        int row, col;
        int max = -1;
        Node node;
        int ttmp, tttmp;
        for (int i = 0; i < n * n; i++) {
            node = al.get(i);
            row = node.row;
            col = node.col;
            ttmp = bamboo[row][col];
            tttmp = route[row][col];
            // 경계값 검사하는거지!!!
            // 윗방향
            if (row - 1 > 0) {
                if (ttmp < bamboo[row - 1][col] && tttmp + 1 > route[row - 1][col]) {
                    route[row - 1][col] = tttmp + 1;
                    max = max > route[row - 1][col] ? max : route[row - 1][col];
                }
            }
            // 오른쪽 방향
            if (col + 1 <= n) {
                if (ttmp < bamboo[row][col + 1] && tttmp + 1 > route[row][col + 1]) {
                    route[row][col + 1] = tttmp + 1;
                    max = max > route[row][col + 1] ? max : route[row][col + 1];
                }
            }
            // 아래방향
            if (row + 1 <= n) {
                if (ttmp < bamboo[row + 1][col] && tttmp + 1 > route[row + 1][col]) {
                    route[row + 1][col] = tttmp + 1;
                    max = max > route[row + 1][col] ? max : route[row + 1][col];
                }
            }
            // 왼족 방향
            if (col - 1 > 0) {
                if (ttmp < bamboo[row][col - 1] && tttmp + 1 > route[row][col - 1]) {
                    route[row][col - 1] = tttmp + 1;
                    max = max > route[row][col - 1] ? max : route[row][col - 1];
                }
            }
        }
        System.out.println(max = (max == -1) ? 1 : max + 1);
    }
}
 
class Node implements Comparable<Node> {
    int bamboo;
    int row;
    int col;
 
    Node(int bamboo, int row, int col) {
        this.bamboo = bamboo;
        this.row = row;
        this.col = col;
    }
 
    public int compareTo(Node n) {
        return this.bamboo - n.bamboo;
    }
}