일단 시작해보는 블로그

[알고리즘_풀이] 프로그래머스 등굣길 java 본문

CS/알고리즘 풀이

[알고리즘_풀이] 프로그래머스 등굣길 java

사용자 Selina Park 2020. 3. 6. 18:49

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

 

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

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매

programmers.co.kr

 

생각

(1, 1)부터 (i, j)까지의 최단 경로 개수 .... (1, 1)부터 (m, n) 최단 경로 개수 이렇게 하나씩 채워나가서 답을 구하는 거니까 DP

 

풀이

  1. d[i][j]의 정의

    d[i][j] : (1, 1) ~ (i, j) 까지, 웅덩이를 지나지 않고 지나갈 때의 최단 거리의 개수

    결국, i=n, j=m 일 때의 값이 답이다.

  2. 웅덩이일 경우 d[][] = -1로 초기화

  3. 비교할 땐, 위쪽 방향과 왼쪽 방향만 비교하면 된다.

    1. 현재 있는 곳이 웅덩이인가?

      → 웅덩이라면 넘어가면 됨.

    2. 왼쪽 방향에 있는게 웅덩이 X?

      → 아니면 더한다. (계속 이거 해줘야 효율성 실패 안뜸 %1000000007)

    3. 윗 쪽 방향에 있는게 웅덩이 X?

      → 아니면 더한다. (계속 이거 해줘야 효율성 실패 안뜸 %1000000007)

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

class Solution {
    // 위, 아래의 경우만 생각해주면 된다.
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        int[][] d = new int[n+1][m+1];
        
        for(int i=0; i<puddles.length; i++) {
            d[puddles[i][1]][puddles[i][0]] = -1;
        }
        
        d[1][1] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(d[i][j] == -1) {
                    continue;
                }
                if(d[i][j-1] >= 0 && d[i][j] >= 0) {
                    d[i][j] += d[i][j-1] %1000000007 ;
                }
                if(d[i-1][j] >= 0 && d[i][j] >= 0) {
                    d[i][j] += d[i-1][j] % 1000000007;
                }
            }
        }

        answer = d[n][m]%1000000007;
        
        return answer;
    }
}
0 Comments
댓글쓰기 폼