[Programmers] 등굣길 - 동적 프로그래밍

🔗 Link

https://school.programmers.co.kr/learn/courses/30/lessons/42898

 

🤔 Think

우아한테크캠프 코딩테스트 문제 중 거의 똑같은 형태의 문제를 풀었던 기억이 있어서 풀이법을 쉽게 떠올릴 수 있었습니다.

 

아래 또는 오른쪽으로만 이동하기 때문에 굉장히 쉽게 풀이가 가능합니다.

 

[a , b]에 도달하는 최단거리는 [a-1 , b]까지 도달하는 최단 거리의 수 + [a , b-1]까지 도달하는 최단 거리의 수 입니다.

 

최단거리로 도달할 수 없는 지역은 -1로 처리했습니다. 0으로 처리하면 초기화 한 이차원 배열에서 초깃값과 구분하기 위해서입니다.

 

이후 2차원 배열을 채워나갑니다. O(N^2)만큼의 시간복잡도가 발생합니다.

🔎 Solve

• n행 m열 크기의 2차원 배열을 생성하고 1행과 1열을 1로 채워줍니다. 
• 최단거리로 도달할 수 없는 지역은 -1로 처리합니다.
  
  • 이 때, 1행과 1열을 다시 돌며 만일 [n-1 , 0] 또는 [0 , n-1] 번 칸이 -1이면 이후 칸은 전부 -1로 처리합니다. 최단거리로 도달할 수 있는 경로가 사라진 것이기 때문입니다.
• 2차원 배열을 돌며 [2,1] 원소부터 순서대로 배열을 채워갑니다.
• 만일 최종 목적지에 도착하는 최소 경로의 수가 없으면 0을 따로 반환합니다.
  • 도착할 수 없는 경우에는 -1이 저장되어 있기 때문입니다.

💻 Code

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

        // 1행 및 1열 초기화
        for (int i = 0; i < n; i++) {
            map[i][0] = 1;
        }
        for (int i = 0; i < m; i++) {
            map[0][i] = 1;
        }

        // 갈 수 없는 위치는 -1로 처리
        for (int[] puddle : puddles) {
            map[puddle[1] - 1][puddle[0] - 1] = -1;
        }

        // 만일 1열 및 1행에서 갈 수 없는 지역이 있으면 이후로도 갈 수 있는 최소 경로는 없음
        for (int i = 1; i < n; i++) {
            if (map[i - 1][0] == -1) {
                map[i][0] = -1;
            }
        }
        for (int i = 1; i < m; i++) {
            if (map[0][i - 1] == -1) {
                map[0][i] = -1;
            }
        }

        // 바로 위 또는 바로 왼쪽 까지 갈 수 있는 최적 경로의 합이 특정 위치까지 갈 수 있는 최적 경로 수
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (map[i][j] == 0) {
                    if (map[i - 1][j] == -1) {
                        map[i][j] = map[i][j - 1];
                        continue;
                    }
                    if (map[i][j - 1] == -1) {
                        map[i][j] = map[i - 1][j];
                        continue;
                    }
                    map[i][j] = (map[i - 1][j] + map[i][j - 1]) % 1000000007;
                }
            }
        }

        // 만일 갈 수 없으면 0 반환
        if (map[n - 1][m - 1] == -1) {
            return 0;
        }
        return map[n - 1][m - 1];
    }
}