등굣길

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

프로그래머스

[문제]

[요약]

격자의 크기인 m, n과 물이 잠긴 지역을 피하여 최소의 지점으로 집에서 학교로 갈 수 있는 경로의 갯수를 반환하라.

 

본 문제는 dp를 이용하여 해결하였습니다. (문제는 기본적인 동적계획법 문제 류중 하나)

1. 처음 방문지점은 집의 위치인 [1,1]일 수 밖에 없다. 따라서 탐색을 진행할때 [1,1] 위치는 제외하고 진행되도록 한다.

2. 처음 방문지점부터 방문처리 dp 배열을 만들어서 경로를 저장하도록 한다.

2. 웅덩이 좌표에 도달하였을 때 dp 배열 위치에 0값을 주어 웅덩이로부터 진행되는 경로를 모두 한정시킨다.

3. 남은 지점에서 진행되는 경로들 위치의 dp 배열값을 이전 경로값과 더해 갱신시킨다.

4. 최종 학교 지점인 [m,n[ 위치까지 도달하면 dp 배열 크기상 dp[m][n] 위치에 모든 최소 거리의 경우가 담기게 된다.

5. 저장된 최단 경로의 개수를 1,000,000,007 값을 modular(%) 한 값을 반환한다.

 

필자의 해결 순서를 이미지로 표현했을때 진행되는 결과

 

	# python
def solution(m, n, puddles):
    field = [[0 for _ in range(n+1)] for _ in range(m+1)]
    field[1][1] = 1
    for i in range(1, m+1):
        for j in range(1, n+1):
            if i == 1 and j == 1: continue
            if [i,j] in puddles: field[i][j] = 0
            else:
                field[i][j] = (field[i-1][j] + field[i][j-1])
    return field[m][n]  % 1000000007
    
    # Java
import java.util.Arrays;
 
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        
        int[][] field = new int[m + 1][n + 1];
        for(int[] arr : field) {
            Arrays.fill(arr, 0);
        }
    
        field[1][1] = 1;
        
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == 1 && j == 1) {
                    continue;
                }
                if(inPuddles(i, j, puddles)) {
                    field[i][j] = 0;
                } else {
                    field[i][j] = (field[i - 1][j] + field[i][j - 1]) % 1000000007;
                }
            }
        }
        return field[m][n] ;
    }
    
    private static boolean inPuddles(int x, int y, int[][] puddles) {
        for (int[] puddle : puddles) {
            if (puddle[0] == x && puddle[1] == y) {
                return true;
            }
        }
        return false;
    }
}