99클럽 코테 스터디 40일차 TIL + 등굣길 (DP)

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 프로그래머스 - 등굣길 (문제 링크)
• 동적 계획법(DP)
• 격자 탐색

 

 

---

 

 

문제 설명

계속되는 폭우로 인해 일부 지역이 물에 잠겨버렸습니다. 이러한 상황에서 집에서 학교까지 가기 위해서는 물에 잠기지 않은 지역을 통과하는 경로를 찾아야 합니다. 주어진 격자에서 오른쪽 또는 아래쪽으로만 이동할 수 있는 상황에서, 집에서 학교까지 갈 수 있는 최단경로의 개수를 구하는 문제입니다.

격자의 크기는 m x n으로 주어지며, 출발지점인 (1, 1)과 도착지점인 (m, n)이 주어집니다. 물에 잠긴 지역은 2차원 배열 puddles로 주어지며, 이 지역은 통과할 수 없습니다. 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 반환해야 합니다.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하입니다.
• 물에 잠긴 지역의 개수는 0개 이상 10개 이하입니다.
• 시작점과 도착점은 물에 잠기지 않습니다.

입출력 예

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

예시 설명

아래와 같은 4x3 격자에서 (2, 2) 위치에 물이 잠겨 있어 이를 피하면서 최단 경로를 찾아야 합니다.

총 4개의 최단 경로가 존재합니다.

 

 

---

 

 

문제 접근

1. 문제 이해
   • 주어진 격자는 2차원 배열로 나타낼 수 있습니다.
   • 물에 잠긴 지역은 이동할 수 없으므로 이를 제외한 경로를 찾아야 합니다.
   • 오른쪽 또는 아래쪽으로만 이동 가능하므로 DP(동적 계획법)을 통해 최단 경로의 개수를 계산할 수 있습니다.
2. 풀이 방법
   • DP 배열을 사용하여 각 지점까지의 최단 경로 개수를 저장합니다.
   • 초기 시작점 (1, 1)에서부터 시작하여 각 칸으로 이동할 때마다 이전 칸에서 오는 경로의 개수를 더해줍니다.
   • 물에 잠긴 지역은 경로의 개수를 1로 표시하여 이를 피할 수 있도록 합니다.
   • 최종적으로 도착지점 (m, n)에 도달했을 때의 값이 최단 경로의 개수입니다.

 

 

풀이 - Java 코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n + 1][m + 1];
        int divide = 1_000_000_007;

        for (int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] = -1;
        }

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

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

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

        return dp[n][m];
    }
}

풀이 설명

1. 초기화
   • dp 배열을 사용하여 각 지점까지의 최단 경로 개수를 저장합니다.
   • puddles 배열에 따라 물에 잠긴 지역을 dp 배열에서 -1 로 표시합니다.
2. DP를 통한 경로 계산
   • dp[1][1]을 시작점으로 설정하고, 이후 오른쪽 및 아래쪽으로 이동하며 최단 경로의 개수를 계산합니다.
   • 이전 칸에서 현재 칸으로 이동할 수 있는 경우, 해당 경로의 개수를 더합니다.
3. 결과 반환
   • 최종적으로 도착지점 (m, n)에 도달했을 때의 dp[n][m] 값을 반환합니다.
     • 이는 최단 경로의 개수를 나타내며, 1,000,000,007로 나눈 나머지를 반환합니다.

 

 

---

 

 

마무리하며

이번 문제는 동적 계획법(DP)을 활용하여 최단 경로를 찾는 문제였습니다.

DP 배열을 사용하여 문제를 효율적으로 해결할 수 있었고, 물에 잠긴 지역을 고려하여 경로를 계산하는 것이 핵심이었습니다.