[JAVA] 등굣길 (코딩테스트 고득점 Kit [ 동적계획법(DP)]) - LEVEL3

📂문제 설명

 

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

 

m         n         puddles  return

4

3

[[2, 2]]

4

입출력 예 설명

 

---

📂아이디어 및 알고리즘(문제 풀이)

• 집에서부터 학교까지 최단경로의 갯 수를 구하면 되는 문제이다. 이 문제에서는 가는 위치마다 "최단 경로"의 수를 저장해주어 학교까지 더해가면 된다. [ DP문제로 쉽게 해결이 가능하다. ]
•  중간에 물 엉덩이가 있을 경우에는 "그 길로 가는 방법의 수는 0"으로 피해가야 한다.
•  DP를 계산 하기 전에 puddles에 있는 배열 값들을 좌표로 DPmap[x][y] = -1 로 해주어 구분지어 준다. [ 물 웅덩이 구분]
• for문을 통해 i,j를 순회하면서 DPmap값들을 더해주어 늘려나간다.
  • DPmap[i]][j] == -1 이면 물웅덩이를 나타내므로 continue를 해준다.
  • DPmap의 값은 해당 위치에서 왼쪽으로의 방향과 위쪽으로의 방향으로만 더해주어야 최단경로를 구할 수 있다.
  • 그래서 왼쪽방향으로의 DPmap[i][j-1]값과 위쪽으로의 DPmap[i-1][j]값을 더해주면 최단경로의 갯 수가 된다. 
  • 물웅덩이가 있는 방향은 더해주지 않고 넘어간다.
• 최종적으로 DP[n][m] 의 값을 출력해주면 된다.

📂소스 코드

class Solution {
    
	static int[][] DPmap;
	public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        DPmap = new int[n+1][m+1];
        //시작점이 [1,1] , 도착점 [n][m];
        // 물 고인점은 puddles지점 
        //DPmap에는 그떄까지의 경로 최솟값을 넣어준다. 
        
        for(int i=0;i<puddles.length;i++) {
        	int y = puddles[i][0];
        	int x = puddles[i][1];
        	DPmap[x][y] = -1;
        	
        }
        DPmap[1][1]=1;
        
        // 간선을 1로 세팅한다. 
      	for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
        		if(DPmap[i][j] == -1) {
        			continue;
        		}
        		//왼쪽 방향 
        		if(DPmap[i][j-1]>=0 && DPmap[i][j]>= 0) {
        			DPmap[i][j] += DPmap[i][j-1] % 1000000007; 
        		}
        		//윗쪽 방향
        		if(DPmap[i-1][j]>=0 && DPmap[i][j] >= 0) {
        			DPmap[i][j] += DPmap[i-1][j] % 1000000007;
        		}
        	}
        }
        return DPmap[n][m]%1000000007;
    }
}

 

📂후 기

앞서 풀었던 DP문제와 유사하여 어렵지 않게 해결했다. (이번건 간결하게~)