99클럽 코테 스터디 40일차 TIL

문제: 학교 가는 길

프로그래머스의 "학교 가는 길" 문제는 학생이 집에서 학교로 가는 경로의 수를 구하는 문제입니다. 학교로 가는 길에는 m x n 크기의 격자가 주어지며, 격자 중 일부는 웅덩이로 막혀 있습니다. 학생은 오른쪽 또는 아래쪽으로만 이동할 수 있으며, 웅덩이를 피해 학교에 도착하는 경로의 수를 구하는 것이 목표입니다.

나의 풀이

이 문제는 동적 프로그래밍(Dynamic Programming)을 활용하여 해결할 수 있습니다. 동적 프로그래밍을 사용하면, 이전까지의 경로를 이용해 현재 위치에서의 경로 수를 효율적으로 계산할 수 있습니다. 이를 위해 dp 배열을 사용하여 각 격자점에서의 경로 수를 저장하고, 웅덩이를 고려하여 경로를 계산합니다.

아래는 이 문제를 해결한 코드입니다:

class Solution {

    public int solution(int m, int n, int[][] puddles) {
        SchoolRoute route = new SchoolRoute(m, n, puddles);
        return route.calculateRoutes();
    }

    class SchoolRoute {

        private int m;
        private int n;
        private int[][] dp;
        private int[][] puddles;

        public SchoolRoute(int m, int n, int[][] puddles) {
            this.m = m;
            this.n = n;
            this.puddles = puddles;
            this.dp = new int[n+1][m+1];
        }

        public int calculateRoutes() {
            dp[1][1] = 1; // 시작점 초기화

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

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (dp[i][j] == -1) { // 웅덩이인 경우 경로 수 0으로 설정
                        dp[i][j] = 0;
                    } else {
                        if (i > 1) {
                            dp[i][j] += dp[i-1][j];
                        }
                        if (j > 1) {
                            dp[i][j] += dp[i][j-1];
                        }
                    }
                }
            }

            return dp[n][m];
        }
    }
}

풀이 설명

1. 초기화:

   • dp 배열은 n+1 x m+1 크기로 생성되며, 각 위치에서의 경로 수를 저장합니다.
   • 시작점 (1, 1)에서 경로 수를 1로 초기화합니다.

2. 웅덩이 설정:

   • puddles 배열을 순회하며, 웅덩이의 위치를 dp 배열에 -1로 표시합니다. 이후 계산 시, 웅덩이는 경로 수가 0이 되도록 처리합니다.

3. 동적 프로그래밍:

   • 두 가지 방향(오른쪽, 아래쪽)으로만 이동할 수 있기 때문에, 현재 위치 (i, j)에서의 경로 수는 위쪽 (i-1, j)과 왼쪽 (i, j-1)에서의 경로 수의 합으로 계산됩니다.
   • 웅덩이가 있는 위치는 경로 수가 0으로 설정되며, 이후 경로 계산에 영향을 주지 않도록 합니다.

4. 결과 반환:

   • 최종적으로 학교의 위치 (n, m)에서의 경로 수가 최종 답이 됩니다.

예제 설명

예를 들어, m = 4, n = 3 크기의 격자에 웅덩이가 있다고 가정해보겠습니다. 웅덩이가 (2, 2)에 있다면, 가능한 경로는 다음과 같이 계산됩니다:

• 시작점 (1, 1)에서 학교 (3, 4)로 가는 경로 중 (2, 2)를 피하면서 도달할 수 있는 모든 경로의 수를 계산합니다.
• 동적 프로그래밍을 통해 각 위치에서의 경로 수를 계산하여 최종적으로 학교에 도달하는 경로의 수를 반환합니다.

회고

효율성 테스트에서 실패하여 내일 다시 효율성을 개선하는 방법을 찾아봐야할 것 같습니다.