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

[프로그래머스]등굣길

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

코딩테스트 연습 - 등굣길

 

풀이

문제 설명이 조금 이상하긴 한데 그림을 보면 m이 세로 행의 개수이고, n이 가로 열의 개수이다. 그러므로 board를 만들때 boar[n][m]으로 만들어 주었다. 이에 따라 puddles의 위치 좌표도 [y, x]좌표로 입력이 되어있다고 생각했다. 그런데 또 문제 설명에서 오른쪽 아래 학교의 좌표는 m, n이라고 한다. 배열로 생각하고 그림을 보면 학교의 좌표는 n, m이 되는데 설명에서는 m, n이라고 되어있다. 즉 문제에서 의미하는 m, n은 일반 배열과 반대로 행의 위치, 열의 위치로 표현되어있다. m, n으로 하든 n, m으로 하든 풀이에는 큰 영향이 없으니 적절하게 풀어주기만 하면 된다. 

 

DP문제 중에 쉬운 편에 속한다고 생각한다. 웅덩이를 피해 오른쪽 아래로 가는 최단경로의 수를 구해주면 된다.

 

그림으로 설명하자면 풀이 과정은 아래와 같다. 문제 설정에 따라 첫 좌표의 위치는 0,0이 아닌 1,1이다. 1,1에서 puddle을 피해 3,4로 가는 모든 최단 경로를 계산한다. 

1,1(start)
	puddle
			3,4(end)

 

이때 3,2위치까지 오는 최단 경로의 수를 계산해 보자. 3,2위치에서 생각해 보면 3,2로 올 수 있는 최단경로는 딱 두가지이다. 위에서 오거나 왼쪽에서 오거나. 오른쪽에서 오면 최단거리가 될 수 없다. 

즉 식으로 작성해 보면) board[i][j] = board[i - 1][j] + board[i][j - 1]이 된다.

근데 이때 조건이 있다. 바로 웅덩이이다. 3,2위치도 위에서 오는 경우는 웅덩이이기 때문에 존재하지 않는다. 그럼 간단하다. 더해주지 않으면 된다. 

즉 board[3][2] = board[3][1]이 된다.

1,1(start)
	puddle
	3,2		3,4(end)

 

일반 점화식은 board[i][j] = board[i - 1][j] + board[i][j - 1]이 될 것이고, board[i][j]가 웅덩이이면 계산을 진행하지 않는다. (최단경로가 존재하지 않으므로)

만약 board[i - 1][j]가 웅덩이가 아니라면 board[i][j]에 더해주면되고,

board[i][j - 1]이 웅덩이가 아니라면 board[i][j]에 더해주면된다. 끝-!

 

코드

import java.util.*;
 
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int mod = 1000000007;
        
        int[][] board = new int[n + 1][m + 1];
        for(int i = 0; i < puddles.length; i++) {
            board[puddles[i][1]][puddles[i][0]] = -1; 
        }
        
        board[1][1] = 1;
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < m + 1; j++) {
                if(board[i][j] == -1) continue;
                if(board[i - 1][j] > 0) board[i][j] += board[i - 1][j] % mod;
                if(board[i][j - 1] > 0) board[i][j] += board[i][j - 1] % mod;
            }
        }
        return board[n][m] % mod;
    }
}