[LeetCode- Part. 1] 6. 최소 경로 합 #

https://leetcode.com/problems/minimum-path-sum/

Minimum Path Sum - LeetCode

 

 

경로를 따라 모든 숫자의 합을 최소화하는 왼쪽 상단에서 오른쪽 하단까지의 경로를 찾기

아래 또는 오른쪽으로 만 이동 가능

 

(1) DFS - 맵

public class Solution {
    public int minPathSum(int[][] grid) {
        Map<Point, Integer> visited = new HashMap<Point, Integer>();
        return findMin(grid, 0, 0, visited);
    }
    
    private int minPathSum(int[][] grid, int x, int y, Map<Point,Integer> visited){
        Point p = new Point(x,y);
        if (visited.containsKey(p)){
            return visited.get(p);
        }
        int min = 0;
        if (x == grid.length-1 && y == grid[0].length-1){
            min = grid[x][y];
        }
        else if(x == grid.length-1){
            min = grid[x][y]+findMin(grid, x, y+1, visited);
        }
        else if(y == grid[0].length-1){
            min = grid[x][y]+findMin(grid, x+1, y, visited);
        }
        else{
            min = grid[x][y] + Math.min(findMin(grid, x+1, y, visited), findMin(grid, x, y+1, visited));
        }
        visited.put(p, min);
        return min; 
    }
    
    private class Point {
        private int x;
        private int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public boolean equals(Object o){
            Point p = (Point)o;
            if (x == p.x && y == p.y){
                return true;
            }
            return false;
        }
        public int hashCode(){return x*100+y;}
    }
}

 

DFS- 배열

public class Solution {
    public int minPathSum(int[][] grid) {
        int[][] visited = new int[grid.length][grid[0].length];
        for (int i=0;i<visited.length;i++){
            for (int j=0;j<visited[0].length;j++){
                visited[i][j]=-1;
            }
        }
        return findMin(grid, 0, 0, visited);
    }
    private int findMin(int[][] grid, int x, int y, int[][] visited){
        if (visited[x][y]!=-1){
            return visited[x][y];
        }
        int min = 0;
        if (x == grid.length-1 && y == grid[0].length-1){
            min = grid[x][y];
        }
        else if(x == grid.length-1){
            min = grid[x][y]+findMin(grid, x, y+1, visited);
        }
        else if(y == grid[0].length-1){
            min = grid[x][y]+findMin(grid, x+1, y, visited);
        }
        else{
            min = grid[x][y] + Math.min(findMin(grid, x+1, y, visited), findMin(grid, x, y+1, visited));
        }
        visited[x][y]=min;
        return min; 
    }
}

 

+) 세련된 풀이

class Solution {
    HashMap<Pair<Integer,Integer>,Integer> memo;
    public int minPathSum(int[][] grid) {
        memo = new HashMap<>();
        return dfs(0,0,grid);
    }
    
    int dfs(int i, int j,int[][]grid){
        if(i==grid.length-1 && j == grid[0].length-1) return grid[i][j];
        Pair<Integer,Integer> cord = new Pair(i,j);
        if(memo.containsKey(cord))return memo.get(cord);
        int fromRight = i!=grid.length-1 ? dfs(i+1,j,grid) : Integer.MAX_VALUE;
        int fromBottom= j!=grid[0].length-1 ? dfs(i,j+1,grid) : Integer.MAX_VALUE;
        int minVal = grid[i][j]+Math.min(fromRight,fromBottom);
        memo.put(cord,minVal);
        return minVal;
    }
}

 

(2) BFS+ 우선순위 큐

 

1. 오른쪽과 아래쪽으로만 이동가능하다

2. 시작점부터 도착점까지의 이동하는 경로의 합 최솟값을 리턴한다.

 

class Solution {
    
    static int m,n;
    static boolean[][] visited;
    static int[][] dirs={{1,0}, {0,1}};
    public int minPathSum(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        visited=new boolean[m][n];
        
        //오름차순 우선순위큐
        Queue<int[]> pq= new PriorityQueue<>((a,b)-> a[2]-b[2]);
        pq.add(new int[] {0,0,grid[0][0]});
        visited[0][0]=true;
        
        //가장 작은 값들이 들어간다.
        while(!pq.isEmpty()){
            int[] cur=pq.poll();
            //0,0,2
            
            for(int[] dir : dirs){
                int x=cur[0]+dir[0];
                int y=cur[1]+dir[1];
                if(x>=0 && y>=0 && x<m&&y<n && visited[x][y]==false){
                    int[] next= new int[]{x,y,cur[2]+grid[x][y]};
                    if(next[0]==m-1 && next[1]==n-1) return next[2];
                    
                    visited[x][y]=true;
                    
                    pq.add(next);
                }
            }
        }
        
        return grid[0][0];
    } 
}

 

 

+) 클래스 사용

class Point{
    public int x, y, value;
    
    Point(int x, int y, int value){
        this.x=x;
        this.y=y;
        this.value=value;
    }
    public boolean equals(Object o){
            Point p = (Point)o;
            if (x == p.x && y == p.y){
                return true;
            }
            return false;
        }
     public int hashCode(){return x*100+y;}
}
class Solution {
    public int minPathSum(int[][] grid) {
        int n=grid.length;
        int m =grid[0].length;
        int[][] dirs = {{1,0},{0,1}};
        boolean [][] visited = new boolean[n][m];
        Queue<Point> pq = new PriorityQueue<>((a,b)-> a.value-b.value);
        Point point = new Point(0,0,grid[0][0]);
        pq.offer(point);
        
        visited[0][0]=true;
        while(!pq.isEmpty()){
            point=pq.poll();
            for(int[] dir : dirs){
                if(point.x+dir[0]>=0&& point.y+dir[1]>=0&&point.x+dir[0]<n&&point.y+dir[1]<m && !visited[point.x+dir[0]][point.y+dir[1]]){  
                
Point np=new Point(point.x+dir[0], point.y+dir[1], point.value+grid[point.x+dir[0]][point.y+dir[1]]);
                    if(np.x==n-1 && np.y==m-1) return np.value;
                    
                    visited[np.x][np.y]=true;
                    pq.offer(np);
                }
                
            }
            
        }
        
        return grid[0][0];
    }
}

---

+) 세련된 코드

1. np를 바로 만들지 않고, 좌표값을 이용해 가능 여부 확인 후 np 생성

2. 작은 값 순서로 뽑은 minheap 이용

import java.util.*;

class Solution {

	int m, n;
	int[][] dirs = { { 1, 0 }, { 0, 1 } };

	public int minPathSum(int[][] grid) {
		// 1.
		m = grid.length;
		n = grid[0].length;
		boolean[][] visited = new boolean[m][n];
		// minHeap
		Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
		pq.add(new int[] { 0, 0, grid[0][0] });
		visited[0][0] = true;

		// 2
		while (!pq.isEmpty()) {
			int[] cur = pq.poll(); // 0,0,2
			for (int[] dir : dirs) {
				int x = cur[0] + dir[0];
				int y = cur[1] + dir[1];

				if (x >= 0 && y >= 0 && x < m && y < n && !visited[x][y]) {
					int[] next = new int[] { x, y, cur[2] + grid[x][y] };
					if (next[0] == m - 1 && next[1] == n - 1) {
						return next[2];
					}
					visited[x][y] = true;
					pq.add(next);
				}

			}

		}
		return grid[0][0];

	}
	
}