<Algorithm> 157. 등산로(SWExpert)

1. 등산로(SWExpert)

   사용 알고리즘 :  DFS, DP, 완전탐색

• 이문제는 푸는데 시간이 많이 걸리지 않았다. 판다 문제유형과 비슷했고 확실하게 어떻게 풀어야하는지 느낌이 와서 그런것 같다.

문제에 대한 접근&생각

1. 길을 찾아야 한다 -> DFS!
2. 최대 팔수 있는 깊이가 주어진다(한번) -> 완전탐색!
3. 현 위치보다 낮은데만 갈수 있음 -> DP!

내 코드 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
 
public class Solution {
    static int n,k;
    static int[][] map,dp;
    static List<Pair> top;
    static final int INF = 99999;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        /******************************
         * 가장 높은 곳의 위치와 크기를 저장한다.
         * 그리고 이를 기준으로 메모라이제이션DP
         * DFS 탐색을 통해서 등산로를 결정한다.
         * 이때 최대 깊이까지 팔 수 있기 때문에  
         * 모든 경우를 탐색한다.
         *******************************/
        for(int t = 1; t <= T; t++) {
            n = sc.nextInt();
            k = sc.nextInt();
            map = new int[n][n];
            dp = new int[n][n];
            
            top = new LinkedList<>();
            int max = 0;
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    map[i][j] = sc.nextInt();
                    if(map[i][j] > max) {
                        max = map[i][j];
                        top.clear();
                        top.add(new Pair(i, j, map[i][j]));
                    }else if(map[i][j]==max) {
                        top.add(new Pair(i, j, map[i][j]));
                    }
                }
            }
            res = 0;
            
            for(int u = 1; u <=k; u++) {
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < n; j++) {
                        map[i][j] -= u;
                        init();
                        solve();
                        map[i][j] += u;
                    }
                }
            }
            
            System.out.println("#"+t+" "+res);
        }
    }
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int res;
    public static void solve() {
        for(int i = 0; i < top.size(); i++) {
            Pair pair = top.get(i);
            if(pair.h != map[pair.x][pair.y]) continue;
            dfs(pair.x, pair.y);
        }
    }
    static boolean[][] visited;
    public static int dfs(int x,int y) {
        if(dp[x][y] != INF) {
            return dp[x][y];
        }
        dp[x][y] = 1;
        for(int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if(isBoundary(nx, ny) && map[x][y] > map[nx][ny]) {
                dp[x][y] = Math.max(dp[x][y],dfs(nx, ny)+1);
                res = Math.max(dp[x][y], res);
            }
        }
        return dp[x][y];
    }
    public static boolean isBoundary(int nx,int ny) {
        if(nx < 0 || ny < 0 || nx >= n || ny >= n) 
            return false;
        return true;
    }
    public static void init() {
        for(int i = 0; i < n; i++) {
            Arrays.fill(dp[i], INF);
        }
    }
    static class Pair{
        int x,y,h;
        public Pair(int x, int y, int h) {
            this.x = x;
            this.y = y;
            this.h = h;
        }
    }
}
 

 

얻은 것

• 2019/03/30 - [공부/Algorithm] - 147. 욕심쟁이판다(BJO) 문제와 비슷한데 이런 문제류 접근하는 법을 알게 되었다.

참고 & 출처