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

 

 

📑 1. 문제설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 

물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 

집에서 학교까지 가는 길은 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

 

입출력 예 설명

---

💡 2. 접근방식

출발지 [1,1]에서부터 웅덩이 puddles[][]를 피해서 도착지 [m,n]로 가는 최단 거리를 1000000007로 나눈 나머지를 구해야한다.

 

아래와 같은 입력 예시로 그림을 만들어 보았다.

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

[3,2]와 [2,4] 좌표에 웅덩이를 지정한다.

그리고 시작점(0, 0)의 크기를 1로 초기화한다.

해당 칸의 값 = 바로 윗칸 값 + 왼쪽 칸 값

이 때 웅덩이는 0으로 계산한다.

1(위쪽) + 0(왼쪽 웅덩이) = 1

최종값인 7을 return한다.

 

 

🐦풀이 과정

1. m, n 크기의 이차원 배열을 만든다. (st[][])
2. 웅덩이 배열(puddles[][]) 크기만큼 반복문을 돌면서 street[][] 배열에서 웅덩이를 -1로 초기화한다. 이 때 배열 인덱스에 주의해야 한다. 인덱스는 0부터 시작하므로 -1을 해 준다.
3. 시작점(0, 0)의 크기를 1로 초기화한다.
4. 이중 for문을 돌며 street[i][j]의 값이 -1이라면(웅덩이) 값을 0으로 바꾼다. 
   i의 값이 0이 아니라면 (맨 위가 아니라면) 위쪽 값을 street[i][j]에 더해준다.
   j의 값이 0이 아니라면 (맨 왼쪽이 아니라면) 왼쪽 값을 street[i][j]에 더해준다.
5. street[m - 1][n - 1]을 리턴한다.

 

✔️ 웅덩이를 처음부터 0으로 초기화하지 않는 이유에 대해

• 웅덩이를 0으로 설정해 버리면, 나중에 경로를 계산할 때 웅덩이인지 아닌지 구분하기 어려우므로 일단은 -1로 설정한다.
• 그러면 이후 경로 계산을 할 때 웅덩이라는 걸 확실하게 알 수 있다.
• 그리고 계산을 할 때 0으로 바꿔준다.

 

 

---

👨‍💻 3. 정답코드

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

    // 웅덩이는 -1로 초기화
    for (int[] puddle : puddles)
      street[puddle[1] - 1][puddle[0] - 1] = -1;

    // 시작점 1로 초기화
    street[0][0] = 1;

    for (int i = 0; i < n; i++) { 
      for (int j = 0; j < m; j++) {

        if(street[i][j] == -1) { // 웅덩이면 0으로 바꾸고 계산 
          street[i][j] = 0;
          continue;
        }

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

    return street[n - 1][m - 1] % 1000000007;
  }
}

✔️ 처음에 틀린 이유

도착지가 m,n 이고 매개변수도 m,n 순서로 받는다.

그래서 아무 생각 없이 배열 선언할 때  int[][] st = new int[m][n]을 했는데 이렇게 하면 틀린다.

 

int[][] st = new int[n][m]; 으로 n이 먼저오고, m이 나중에 온다. 

문제에서 m은 가로(열), n은 세로(행)이기 때문이다.

Java의 배열은 st[row][col] 형태로 행렬이다. 

 

👏🏻 4. 개선된 코드

public class Solution {
  public int solution(int m, int n, int[][] puddles) {
    int MOD = 1_000_000_007;
    int[][] street = new int[n][m];

    // 웅덩이를 -1로 초기화
    for (int[] puddle : puddles)
      street[puddle[1] - 1][puddle[0] - 1] = -1;

    // DP 시작점
    street[0][0] = 1;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (street[i][j] == -1) { // 웅덩이면 0으로 변경
          street[i][j] = 0;
          continue;
        }
        
        if (i > 0) street[i][j] = (street[i][j] + street[i - 1][j]) % MOD;
        if (j > 0) street[i][j] = (street[i][j] + street[i][j - 1]) % MOD;
      }
    }
    return street[n - 1][m - 1];
  }
}

🔍 chatGPT에 코드 리뷰 & 개선점

1. 모듈러 연산 (% 1000000007) 위치 조정
기존에는 street[i][j] += street[i - 1][j] % 1000000007; 이렇게 작성되어 있다.

하지만 실제론느 모듈러 연산을 더한 후에 적용해야 정확하다고 한다.

(A + B) % C는 (A % C + B % C) % C와 같으므로, 최종 값에서만 % 1000000007 하면 된다고 한다.

지금 방식도 큰 문제는 없지만, 불필요한 모듈러 연산이 늘어난다.

 

2. 불필요한 street[0][0] = 1;
street[0][0]을 1로 초기화했는데, 이걸 안에 포함시키는 방식도 가능하다. 
어차피 i == 0이거나 j == 0이면 위나 왼쪽 값이 없으므로, 따로 처리해 줄 수도 있다고 한다. 

---

🐦 5. TMI

너무 어렵다.