🏫문제

프로그래머스-등굣길

다이나믹 프로그래밍이란?
특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

최단경로 문제도 기존 경로 값을 이용하여 쉽게 구할 수 있다.

🏫풀이

예제의 기본 테스트케이스를 준비했다.
아래의 지도에 경로의 수를 기록하면 된다.

1. 초기화

  • 시작점은 (1,1)로 정해져 있으므로 첫칸(1,1)은 "1"로 설정한다.
  • 웅덩이를 식별하기 위해 음수 "-1" 로 설정한다.
  • 편의를 위해 0번째 행과 열은 비워둔다. (깍두기)

2. 경로 계산

  • 등굣길은 오른쪽과 아래 방향으로만 갈 수 있으므로

  • 이 길을 지나갈 수 있는 경우의 수 = 위쪽 길의 경우의 수 + 왼쪽 길의 경우의 수

  • 첫칸(1,1)은 생략하고 왼쪽부터 아래로 차례대로 왼쪽과 위쪽의 값을 더해준다.

  • 웅덩이가 나오면 0으로 설정해주고 더한다.
    첫번째 열과 첫번재 행의 계산을 편하게 하기 위해 '2.초기화' 과정에서 깍두기 줄을 추가 해줬다.

3. 정답은 4!!

코드


public int solution(int m, int n, int[][] puddles) {
    //배열 생성 및 초기화
    int[][] route = new int[m+1][n+1];

    route[1][1] = 1;
    
    /* 2. 웅덩이 -1 으로 표시 */
    for(int[] p : puddles) {
    	int i = p[0];
    	int j = p[1];
    	route[i][j] = -1;
    }

    /* 3. 경우의 수 계산 */
    for(int i=1 ; i <= m ; i++) {
    	for(int j=1 ; j <= n ; j++) {
    		if(i == 1 && j == 1) continue; //첫칸은 생략
    		if(route[i][j] < 0) {//웅덩이
    			route[i][j] = 0;
    			continue; 
    		}
			route[i][j] = (route[i][j-1]  % 1000000007) + (route[i-1][j] % 1000000007);
    	}
    }

    return route[m][n] % 1000000007;
}

0개의 댓글