[ DP ] - 등굣길(DP)

문제

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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 이하인 자연수입니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

입출력 예 설명

 

풀이

1. 오른쪽 / 아래쪽으로 만 움직이고, start를 1로 설정

2. 물 웅덩이의 좌표 값이 나와 있으므로 해당 구역을 -1로 초기화

3. 배열 반복문을 통해 물웅덩이일 경우 0으로 변경 후, 해당 인덱스 위치 값일 경우 왼쪽값과 위쪽값을 더해서 나온 값이 최단거리로 가는 경우의 수 값이다.

4. 특정 위치(x,y)로 가기 위한 최단 거리는 (x-1,y)까지 가는 최단거리(아래) + (x,y-1)까지 가는 최단거리(오른쪽)의 합이다. 그로 인해 점화식이 도출된다.

5. 문제에서 m,n의 가 반대로 나와있는데 반대로 나와있는게 함정인줄 알았으나 실제 테스트 케이스는 반대로 안되어있다.....문제수정...필요, 그래서 코드가 2개이다.

6. 배열 값과 return 값에 1,000,000,007 로 나머지 연산을 하는 이유는 m,n이 100일 경우 값이 int 범위를 벗어나서 값을 조절을 위해 해준다....

코드

import java.util.Arrays;

public class School {
	public static void main(String[] args) {
		int m=4;
		int n=3;
		int[][] puddles= {{2,2}};
		solution2(m,n,puddles);
	}
	public static void solution(int m, int n, int[][] puddles) {
		//mn의 배열 인덱스가 반대
		int[][] map = new int[n][m];
		// 웅덩이 -1
		for(int i=0; i<puddles.length; i++) {
			int x = puddles[i][0]-1;
			int y = puddles[i][1]-1;
			map[x][y] = -1;
		}
		//[[0, 0, 0, 0], [0, -1, 0, 0], [0, 0, 0, 0]]
		System.out.println(Arrays.deepToString(map));
		// start 는 1
		map[0][0] = 1;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j] == -1) {
					map[i][j] = 0;
					continue;
				}
				if(i != 0) {// 맨위가 아닌경우 위쪽값을 더해준다. 
					map[i][j] += map[i-1][j] % 1000000007;
				}
				if(j != 0) {// 맨왼가 아닌경우 왼쪽값을 더해준다.
					map[i][j] += map[i][j-1] % 1000000007;
				}
			}
			
		}
		System.out.println(Arrays.deepToString(map));
//		[[1, 1, 1, 1],[1, 0, 1, 2],[1, 1, 2, 4]]
		// 4,3 위치의 값
		System.out.println(map[n-1][m-1] % 1000000007);
		
	}
    public static void solution2(int m, int n, int[][] puddles) {
        int[][] map = new int[m][n];
		for(int i=0; i<puddles.length; i++) {
			int x = puddles[i][0]-1;
			int y = puddles[i][1]-1;
			map[x][y] = -1;
		}
        System.out.println(Arrays.deepToString(map));
        //[[0, 0, 0], [0, -1, 0], [0, 0, 0], [0, 0, 0]]
        map[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
				if(map[i][j] == -1) {
					map[i][j] = 0;
					continue;
				}
				if(i != 0) {// 맨위가 아닌경우 위쪽값을 더해준다. 
					map[i][j] += map[i-1][j] % 1000000007;
				}
				if(j != 0) {// 맨왼가 아닌경우 왼쪽값을 더해준다.
					map[i][j] += map[i][j-1] % 1000000007;
				}
            }
        }
        System.out.println(Arrays.deepToString(map));
		//[[1, 1, 1], [1, 0, 1], [1, 1, 2], [1, 2, 4]]
        System.out.println(map[m-1][n-1]%1000000007);
    }
}