[프로그래머스 level_3] 등굣길 for JAVA

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

프로그래머스

[문제 설명]

 

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

입출력 예 설명

[풀이]

dp를 사용해서 문제를 해결했다. 다만 인덱스 관리가 조금 번거로워서 주어진 m, n에 1씩 인덱스를 추가해서 해결했다.

주어진 경로 한 셀마다 이 길을 지나가는 경우의 수를 표시하기 위해 각 경로들이 만나는 지점에서 경우의 수를 증가시켜줬다.

 

[코드]

    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n + 1][m + 1];
 
        // 웅덩이 부분 -1로 초기화하기
        for (int i = 0; i < puddles.length; i++) {
            int k = puddles[i][0];
            int j = puddles[i][1];
 
            map[j][k] = -1;
        }
        
        //집은 1
        map[1][1] = 1;
        
        for (int i = 1; i < map.length; i++) {
            for (int j = 1; j < map[0].length; j++) {
                if (map[i][j] == -1) {                                //웅덩이를 만나면 0으로 초기화
                    map[i][j] = 0;
                } else {                                            
                    map[i][j] += map[i - 1][j] % 1000000007;        //어느 한 지점은 위에서 오는 경우와 왼쪽에서 오는 경우의 합
                    map[i][j] += map[i][j - 1] % 1000000007;
                }
            }
        }
        return map[n][m] % 1000000007;
    }

프로그래머스 테스트 케이스 통과

 

느낀 점 : 처음에 조금 헤매다가 다른 분이 작성한 코드를 보고 공부하고 이해한 다음 나만의 코드를 작성해보았다. 다만 궁금증이 든 것은 만약에 최소한의 거리가 웅덩이 때문에 지도상 위로 올라가는 루트가 있다면은 그때는 최솟값이 안 나오지 않을까라는 궁금증이 들어 이 문제를 해결해볼 만한 방법들을 생각해봐야겠다.

 

오랜만에 다시 풀어봤다. 이 문제를 풀 당시에는 다른 사람의 문제풀이를 보고 공부했는데, 지금은 얼마 안걸려서 문제를 풀었다. 이때가 가장 보람찬 것 같다. 그리고 당시 풀 때 지도상 위로 올라가는 루트에 대해 고민했었는데 문제에 "오른쪽과 아래방향으로만 움직일 때"란 추가 설명이 생겼다. 나와 같은 사람이 더 있었던 것이다ㅋㅋ..