등굣길 : DP (Level 3)

이번문제는 생각보다 애를 먹은 문제입니다.

 

처음에는 DPS로 최단경로를 구하였으나, 효율성 문제 실패로 인해 DP로 다시 풀어보았습니다.

 

물론 DP로 풀때는 다른 분들의 로직을 참고하였습니다.

 

이번문제는 m,n의 값이 반대인 경우라 조금 헷갈리는 부분이 있었습니다.

 

하지만 한번 이해하면 그다지 어려운 문제는 아니라 생각합니다.

 

2차원 배열에서의 해당 위치까지오는 최단 경로 구하는 문제의 핵심은

해당 위치까지 오는 최단 경로의 수 = 그 전(상/좌) 경로의 수의 합 이라는 것을 생각하면 됩니다.

 

또한 효율성을 위해 1,000,000,007을 매번 계산하여 구하는 것 보다 해당 값을 넘는 경우만 나머지를 구하여 적용하면 보다 더 효율적인 코드가 됩니다. 

import java.util.*;

class Solution {
	public int solution(int m, int n, int[][] puddles) {
		int answer = 0;

		int[][] map = new int[n][m]; // (m,n반대 주의***)
		map[0][0] = 1; // 기본설정

		// 물 웅덩이 표시 (m,n반대 주의***)
		for (int i = 0; i < puddles.length; i++) {
			map[puddles[i][1] - 1][puddles[i][0] - 1] = -1; // 기본 초기화가 0이므로 구분을 위해 -1로 적용
		}

		// 경로 구하기 (m,n반대 주의***)
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {

				if (map[i][j] == -1) { // 물 웅덩이인 경우
					map[i][j] = 0; // 점화식 계산을 위해 해당 경로는 오는 경우가 없으므로 0 처리
					continue;
				}
				/*
				 * 해당위치까지 오는 경로 = 상측 경로 수 + 좌측 경로 수
				 * 단, map의 범위를 벗어나는 경우는 제외하고 계 
				 */
				if (i - 1 >= 0) { // 범위체크
					map[i][j] += map[i - 1][j]; // 상측 경로 수  
				}
				if (j - 1 >= 0) { // 범위체크
					map[i][j] += map[i][j - 1]; // 좌측 경로 수
				}
                
				// 효율성을 위해 해당경우만 나머지 적용 (매번 적용하면 비효율)
                if(map[i][j] >= 1000000007){ 
                    map[i][j] = map[i][j] %1000000007;
                }
			}
		}
		answer = map[n - 1][m - 1];
		return answer;
	}
}