[프로그래머스] 등굣길 문제

동적프로그래밍을 활용하는 Lv3문제입니다.

---

<문제 설명>

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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

입출력 예 설명

---

< 내 풀이 >

문제를 보자마자 초등학교 때 풀던 수학문제집 생각이 나면서

풀이를 단번에 생각해냈다 ㅎ.. 정말 뜻밖의 기억이었지만 초등수학에 길찾기 경우의 수 문제가 있당ㅎ

꼭 길 중간에 물웅덩이가 있거나 공사중이다ㅎㅎ^-^..

 

위의 테스트 케이스로 생각한다면,

출발지에서 도착지까지 우측과 아래 두가지 방향으로만 움직일 수 있으며

연속적으로 한쪽방향으로만 움직일때는 단 1가지의 방법만 존재할 것이다.

따라서 아래 표와 같다. X는 물이 잠긴 지역의 위치이다.

출발	1	1	1
1	X	P
1			도착

이때 간단하게 P지점까지의 경로를 먼저 생각해보자

웅덩이는 지날 수 없기 때문에 X를 지나가는 경우의 수는 0이라고 볼 수 있다.

또한 특정 지점에 접근해 오는 방향은 좌측과 위쪽 뿐이다.

그러므로 특정 지점까지 도달하는 경우의 수 = (윗 지점까지의 경우의 수) + (좌측 지점까지의 경우의 수)이다.

출발	1	1	1
1	X=0	P=(1+0)
1			도착

 

이 공식과 같은 과정을 반복해 도착 지점까지의 경우의 수를 구하면 된다.

이때 고려해야할 것이 있다.

아래 표처럼 웅덩이가 1행이나 1열에 존재한다면

그 지점 이후부터는 동일방향으로 움직이는 경로가 0이된다는것을 인지해야한다.

출발	1	X	0
1	X
1			도착

이런 경우를 고려해서 코드를 작성했다.

 

<코드>

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[m][n];
        map[0][0]=1;	//출발지점을 0이라고 치기
        
        // 웅덩이 체크
        for(int[] puddle : puddles){
            map[puddle[0]-1][puddle[1]-1] = -1;
        }
        
        //(0,n) 1행 초기화
        int status = 1;
        for(int k=1; k<n; k++){
            if(map[0][k]==-1){	//웅덩이가 존재하면 해당지점 이후부터는 경우의수가 0이 됨
                status=0;
            }
            map[0][k]=status;
        }
        //(m,0) 1열 초기화
        status = 1;
        for(int l=1; l<m; l++){
            if(map[l][0]==-1){
                status=0;
            }
            map[l][0]=status;
        }
        
        //거리계산
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(map[i][j]==-1){
                    map[i][j]=0;
                }
                else{
                    map[i][j]=(map[i-1][j]+map[i][j-1])%1000000007;
                }
            }
        }
        
        return map[m-1][n-1];
    }
}

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길 | 프로그래머스