[프로그래머스] 등굣길(동적계획법)

프로그래머스

동적계획법(Dynamic Programming)

 

프로그래머스

등굣길

 

문제 정리

1. m : 가로 / n : 세로
2. 집 : 가장 왼쪽 위 (1,1)→배열(0,0)에 해당 / 학교 : 가장 오른쪽 아래(m, n)→배열(n-1, m-1) 해당
3. 물이 잠긴 지역의 조료를 담은 2차원 배열 매개변수 puddles
4. 오른쪽과 아래쪽으로만 움직여서 학교까지 갈 수 있는 최단 경로
5. return : 최단경로 % 1000000007

 

 

시작하기 전 접근 방법

1. 최단 경로를 구하는 문제이다.
2. 최단 경로를 구하기 위해서는 각 구간마다 갈 수 있는 최단 경로를 구하여 나아가는 방법을 사용해야 한다.
3. 물이 있는 경로는 갈 수 없는 경로며 해당 경로를 지나서 다음 경로를 갈 수 있는 방법은 없기 때문에 경로 값을 0으로 설정한다.
4. 오른쪽과 아래로만 갈 수 있기 때문에 dp [i][j] = dp [i-1][j] 값과 dp [i][j-1]을 합하는 값이다.
5. 물웅덩이가 없다면 가장 윗부분과 왼쪽 부분으로 가는 최단 경로는 직선뿐이므로 값은 1이다. 
6. x칸에 해당하는 경로를 구하는 방법은 x기준으로 왼쪽과 윗부분을 더하면 해당 경로로 갈 수 있는 최단 경로를 찾는 규칙이 나온다.

 

 

물 웅덩이가 없을 때 경우의 수

물웅덩이가 있을 경우

 

1. 규칙을 통해 구해지는 경로를 저장할 2차원 배열을 만들고 물 웅덩이 위치가 주어지는 매개변수 2차원 배열을 경로 저장 배열에 저장한다.
2. 0부터는 해당 칸에 갈 수 있는 경로이기 때문에 -1로 구분하여 물웅덩이가 있는 좌표임을 나타낸다.
3. 집 위치인 (0,0)은 해당 경로를 1로 구분한다.

int[][] dp = new int[n][m];
for (int[] puddle : puddles)
	dp[puddle[1] - 1][puddle[0] - 1] = -1;
	dp[0][0] = 1;

 

 

4. 이제 규칙을 알았으니 적용할 차례다! 반복문을 통해서 칸에 들어갈 값을 설정한다.
4-1. 쉽게 (x, y)에 값은 (x-1, y) + (x, y-1) 값이다. 하지만 x에 0 또는 y에 0이 들어가면 배열 인덱스에 벗어나기 때문에 예외가 발생한다.
4-2. 따라서 각각 x가 0이 아닐 때, y가 0이 아닐 때 계산해 줘서 맨 윗부분과 가장 왼쪽 부분도 채워준다.

if (i != 0) {
	dp[i][j] += dp[i - 1][j]% 1000000007;
}

if (j != 0) {
	dp[i][j] += dp[i][j - 1]% 1000000007;
}

 

실수했던 부분으로 이 부분에서 1000000007을 나눠주지 않으면 효율성 검사에서 통과하지 못하고 실패한다!!

 

 

5. 반복문을 통해서 각 구간마다 최단 경로 값을 구해준다.
5-1. 여기서 물웅덩이 부분을 지나갈 수 없고 해당 경로를 통해서 갈 수 있는 최단 경로가 없기 때문에 저장해 뒀던 dp배열에서 값이 -1이 나오는 구간은 경로가 없다는 의미로 값을 0으로 바꾸고 반복문을 넘어간다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (dp[i][j] == -1) {
			dp[i][j] = 0;
			continue;
		}
	}
}

 

 

실수했던 부분

1. 처음 코드를 작성해 볼 때 가장 왼쪽과 위쪽 부분을 다 1로 채운다음 같은 방식을 이용하여 진행했었다. 이렇게 하면 채점 전 테스트 코드는 통과하지만 채점 테스트 코드와 효율성은 완전 꽝이 나온다. 이걸 통해서 규칙이 있다면 최대한 모든 부분은 규칙을 이용해서 채워야 한다는 것을 생각하게 되었다.
2.  (4) 번에 해당하는 부분을 한 번에 처리할려고 했던 것도 문제였다. 인덱스 범위가 벗어나는 경우도 있고 임의로 채우지 않으면 (0,Y) 와 (X,0)부분에 어떻게 채워야 하는지도 문제였다. 해결하기 위해서는 한번에 하는 것이 아닌 답처럼 나눠서 처리해야 하는 방법이었다.
3. dp배열에 값을 1000000007 이것으로 나누지 않으면 효율성 점수도 빵점이었다.

 

 

처음 작성한 잘못된 코드

가로와 세로가 0인 부분에는 물웅덩이가 존재한다는 부분을 빼먹었다...

class Solution {
    public int solution(int m, int n, int[][] puddles) {
    int[][] dp = new int[n][m];
        dp[0][0] = 0;
        
        for(int i=1; i<m; i++){
                dp[0][i] = 1;
        }
        for(int i=1; i<n; i++){
                dp[i][0] = 1;
        }
        for(int i=0; i<puddles.length;i++){
            int x = puddles[i][0];
            int y = puddles[i][1];
            dp[x-1][y-1] = -1; 
        }
        
        for(int i=1; i<n; i++){
            for(int j=1; j<m; j++){
            	if(dp[i][j]==-1) {
            		dp[i][j]=0;
            		continue;
            	}else {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            	}
            }
        }
        
        int answer = dp[n-1][m-1]%1000000007;
        return answer;
    }
}

 

최종 코드

class Solution {
	public int solution(int m, int n, int[][] puddles) {
		int[][] dp = new int[n][m];
		for (int[] puddle : puddles)
			dp[puddle[1] - 1][puddle[0] - 1] = -1;
		dp[0][0] = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (dp[i][j] == -1) {
					dp[i][j] = 0;
					continue;
				}
				if (i != 0) {
					dp[i][j] += dp[i - 1][j]% 1000000007;
				}

				if (j != 0) {
					dp[i][j] += dp[i][j - 1]% 1000000007;
				}

			}

		}
		int answer = dp[n - 1][m - 1] % 1000000007;
		return answer;
	}
}