2024.03.15 - path-with-minimum-effort

[wlsgh7608]

문제 - 링크

문제 풀이

• (0,0) -> (N-1,M-1)로 이동할 때 최소의 노력으로 이동하기
• 여기서 최소의 노력이란, 경로상 연속된 칸들의 차이 중 가장 큰 차이 값을 의미

간단한 DFS을 통하여 계산(실패)

• DFS을 돌리며 현재보다 최소의 노력일 때만 진행하도록 수행

            int nextHeight = heights[nx][ny];
            int diffHeight =Math.abs(nextHeight - currentHeight);
            int maxEffort = Math.max(effort, diffHeight);
            // 현재보다 노력이 큰 경우 더이상 진행하지 않음
            if(maxEffort>=minEffort[nx][ny])           {
                continue;
            }
            dfs(nx, ny, maxEffort, heights);

DFS 코드

    void dfs(int x,int y, int effort,int[][] heights){

        minEffort[x][y] = Math.min(minEffort[x][y],effort);
        if(x == N-1 && y== M-1){
            return;
        }

        int currentHeight = heights[x][y];

        for(int i = 0; i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<0|| ny<0 || nx>=N|| ny>=M ) {
                continue;
            }
            int nextHeight = heights[nx][ny];
            int diffHeight =Math.abs(nextHeight - currentHeight);
            int maxEffort = Math.max(effort, diffHeight);
            // 현재보다 노력이 큰 경우 더이상 진행하지 않음
            if(maxEffort>=minEffort[nx][ny]){
                continue;
            }
            dfs(nx, ny, maxEffort, heights);
        }
    }

�실패

• 시간초과 발생

시간 초과 발생 원인

• 특정 노드의 값에 노력의 값이 내림차순으로 진행되는 경우 불필요한 연산을 계속 수행하는 문제가 있음
• 노력의 값이 최소인 것부터 연산을 수행하자(Dijkstra)

[wlsgh7608]

문제 해결

• 노력의 값이 최소인 것 부터 연산을 수행하자(Dijkstra)

노력의 값이 최소인 것부터 정점을 사용하도록 클래스 생성

• Comparable 인터페이스를 구현

    class Node implements Comparable<Node> {
        int x;
        int y;
        int effort;

        public Node(int x, int y, int effort) {
            this.x = x;
            this.y = y;
            this.effort = effort;
        }

        @Override
        public int compareTo(Node o) {
            return this.effort - o.effort;
        }
    }

dijkstra 코드

    void dijkstra(int[][] heights){

        Queue<Node> PQ = new PriorityQueue<>();
        minEffort[0][0] = 0;
        PQ.add(new Node(0, 0, 0));

        while(!PQ.isEmpty()){
            Node cur = PQ.poll();
            int x = cur.x;
            int y= cur.y;
            int effort = cur.effort;

            // 끝에 도달한 경우
            if(x==N-1 && y==M-1){
                PQ.clear();
                return;
            }


            int currentHeight = heights[x][y];
            for(int i = 0 ; i<4;i++){
                int nx = x+dx[i];
                int ny=  y+dy[i];

                if(nx<0|| ny<0 || nx>=N|| ny>=M ) {
                    continue;
                }
                int nextHeight = heights[nx][ny];
                int diffHeight =Math.abs(nextHeight - currentHeight);
                int maxEffort = Math.max(effort, diffHeight);

                // 지금보다 노력의 값이 작은 경우에만 진행
                if(maxEffort<minEffort[nx][ny]){
                    minEffort[nx][ny] = maxEffort;
                    PQ.add(new Node(nx, ny, maxEffort));
                }
            }
        }
    }

전체 코드

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution2 {
    class Node implements Comparable<Node> {
        int x;
        int y;
        int effort;

        public Node(int x, int y, int effort) {
            this.x = x;
            this.y = y;
            this.effort = effort;
        }

        @Override
        public int compareTo(Node o) {
            return this.effort - o.effort;
        }
    }

    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    int N;
    int M;

    int[][] minEffort;

    void dijkstra(int[][] heights){

        Queue<Node> PQ = new PriorityQueue<>();
        minEffort[0][0] = 0;
        PQ.add(new Node(0, 0, 0));

        while(!PQ.isEmpty()){
            Node cur = PQ.poll();
            int x = cur.x;
            int y= cur.y;
            int effort = cur.effort;

            // 끝에 도달한 경우
            if(x==N-1 && y==M-1){
                PQ.clear();
                return;
            }


            int currentHeight = heights[x][y];
            for(int i = 0 ; i<4;i++){
                int nx = x+dx[i];
                int ny=  y+dy[i];

                if(nx<0|| ny<0 || nx>=N|| ny>=M ) {
                    continue;
                }
                int nextHeight = heights[nx][ny];
                int diffHeight =Math.abs(nextHeight - currentHeight);
                int maxEffort = Math.max(effort, diffHeight);

                // 지금보다 노력의 값이 작은 경우에만 진행
                if(maxEffort<minEffort[nx][ny]){
                    minEffort[nx][ny] = maxEffort;
                    PQ.add(new Node(nx, ny, maxEffort));
                }
            }
        }
    }

    private void init(int[][] heights){
        N = heights.length;
        M = heights[0].length;
        minEffort = new int[N][M];
        for(int[] row : minEffort){
            Arrays.fill(row, 1_000_000);
        }
    }


    public int minimumEffortPath(int[][] heights) {
        init(heights);
        dijkstra(heights);
        return minEffort[N-1][M-1];
    }

}

시간, 공간 복잡도

• 정점의 수 : N, 간선의 수 : E
• 시간 복잡도 : O(ElogV)
• 공간 복잡도 :

결과