[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 등굣길

📚 문제 설명

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

• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

 

🎯 어떻게 풀었나

첫번째 시도 (50/ 100) - 효율성 통과🙅🙅‍♀️🙅‍♂️

class Solution {
    private static final boolean PUDDLE  = true;
    
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        long[][] route = new long[m + 1][n + 1]; // default : 0
        boolean[][] map = new boolean[m + 1][n + 1]; // default : false
        
        // init map
        for(int i = 0; i < puddles.length; i++) {
            int x = puddles[i][0];
            int y = puddles[i][1];
            
            map[x][y] = PUDDLE;
        }
        
        for(int i = 1; i < route.length; i++) {
            for(int j = 1; j < route[i].length; j++) {
                if(i == 1 && j == 1) {
                    route[i][j] = 1;
                    continue;
                }
                
                if(map[i][j] == PUDDLE) continue;
                
                route[i][j] = route[i - 1][j] + route[i][j - 1]; // from left + from top
            }
        }
        
        answer = (int)(route[m][n] % 1000000007);
        
        return answer;
    }
}

 

최종 코드

class Solution {
    private static final int PUDDLE = -1;
    
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] map = new int[m + 1][n + 1]; // default : 0
            
        // init map
        for(int i = 0; i < puddles.length; i++) {
            int x = puddles[i][0];
            int y = puddles[i][1];
            
            map[x][y] = PUDDLE;
        }
        
        for(int i = 1; i < map.length; i++) {
            for(int j = 1; j < map[i].length; j++) {
                if(i == 1 && j == 1) {
                    map[i][j] = 1;
                    continue;
                }
                
                if(map[i][j] == PUDDLE) {
                    map[i][j] = 0;
                    continue;
                }
                
                map[i][j] = (map[i - 1][j] + map[i][j - 1]) % 1000000007; // from left + from top
            }
        }
        
        answer = map[m][n];
        
        return answer;
    }
}

 

🧐 왜 저렇게 풀었나

첫번째 시도 (50/ 100) - 효율성 통과🙅🙅‍♀️🙅‍♂️

이 문제를 접근하기 위해서는 몇 가지 배경지식이 필요하다.

먼저 Top left로부터 bottom right까지 최단 경로의 개수를 구해야 하기 때문에 최단 경로로 이동하기 위해서는 아래, 오른쪽 이동만 해야 한다.

그리고 아래, 오른쪽 이동만 할 수 있기 때문에 한 지역에 도달하기 까지의 최단 경로의 개수는 (윗 지역의 최단 경로의 개수) + (왼쪽 지역의 최단 경로의 개수)이다. 하지만 만약 그 지역이 물웅덩이라면 최단 경로를 계산하지 않고 0으로 두어야 한다.

 

위와 같은 배경지식을 이용해서 코드를 작성했다. 하지만 결과는 효율성 실패였다...😂

 

최종 코드

아무리 생각해도 알고리즘의 결함은 없었다. 그래서 질문하기를 봤는데 overflow가 안 생기도록 modulo 연산을 미리 하면 통과한다고 한다. 그래서 그 방법대로 코드를 작성했고 통과했다😄

 

📖 무엇을 배웠나

Type의 범위에 관해서 늘 고려하는 습관을 가지자!