[프로그래머스] 등굣길 - Java

문제

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

프로그래머스

 

---

문제 개요

계속되는 폭우로 인해 일부 지역이 물에 잠겼습니다. 우리는 물에 잠기지 않은 지역을 통해 집에서 학교까지 가는 최단 경로의 개수를 구하려고 합니다. 집은 격자의 왼쪽 위에 있고, 학교는 오른쪽 아래에 위치합니다. 경로는 오른쪽과 아래쪽으로만 이동할 수 있으며, 물에 잠긴 지역을 피해야 합니다. 이 문제는 주어진 격자의 크기와 물에 잠긴 지역을 고려하여 최단 경로의 개수를 계산하는 문제입니다.

 

접근 방법

1. 격자 관리 및 물에 잠긴 지역 설정: 먼저, 격자를 생성하고 물에 잠긴 지역의 좌표를 표시합니다. 물에 잠긴 지역은 경로 탐색에서 제외됩니다.
2. 경로 계산 로직 구현: 집에서 학교까지 이동하는 동안 오른쪽과 아래쪽으로만 이동할 수 있으므로 각 위치에서 이동 가능한 경로의 개수를 누적하여 계산합니다. 이를 위해 동적 계획법(DP)을 사용합니다.
   • 시작 위치에서 경로 개수를 1로 설정하고, 이후 경로를 오른쪽과 아래쪽으로 누적하면서 계산합니다.
   • 물에 잠긴 지역은 경로 계산에서 제외하고, 해당 좌표를 0으로 설정하여 더 이상 이동할 수 없도록 합니다.
3. 경로 개수 모듈러 연산: 경로의 개수를 1,000,000,007로 나눈 나머지 값을 반환하도록 하여 큰 수를 처리합니다.

 

해결 과정

1. 격자 및 초기값 설정: 주어진 격자의 크기와 물에 잠긴 지역을 바탕으로 2차원 배열을 생성합니다. 각 위치의 경로 개수를 저장하며, 집의 위치를 1로 설정하여 경로 탐색을 시작합니다.
2. 동적 계획법을 활용한 경로 탐색: 각 위치에서 오른쪽과 아래쪽으로 이동할 수 있는 경로의 개수를 누적하며 계산합니다. 물에 잠긴 지역은 제외합니다.
3. 최종 계산 및 반환: 학교에 도달할 수 있는 경로의 총 개수를 계산한 후, 이를 반환합니다. 이때 경로의 개수는 문제에서 주어진 1,000,000,007로 나눈 나머지 값으로 처리합니다.

 

주의할 점

초기 입력값 m과n 그리고 puddles 의 행렬의 순서 주의

 

import java.util.*;
class Solution {
    final int MOD = 1_000_000_007;
    int[][] map;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        map = new int[n+1][m+1];
        map[1][1] = 1;
        
        for(int i=0; i<puddles.length; i++) {
            map[puddles[i][1]][puddles[i][0]] = -1;
        }
        
        for(int i=1; i<map.length; i++) {
            for(int j=1; j<map[i].length; j++) {
                if(i==1 && j==1) continue;
                if(map[i][j] == -1) continue;
                
                map[i][j] = ((map[i-1][j] == -1 ? 0 : map[i-1][j]) + (map[i][j-1] == -1 ? 0 : map[i][j-1])) % MOD;
            }
        }
        answer = map[n][m];
        return answer;
    }
}