프로그래머스 - 등굣길 연습

오늘 풀어볼 문제는 ⭐등굣길 연습 입니다!

문제는 간단합니다.

다음과 같이 집, 학교, 웅덩이가 있습니다. 웅덩이를 피해 학교까지 갈 수 있는 경우의 수를 구하면 됩니다.

이와 비슷한 문제를 풀었던 기억이 있어, 접근법은 금방 생각났습니다. 복습용으로 아주 좋았습니다ㅎㅎ

비슷한 문제는 프로그래머스 - 보행자 천국 이었습니다! 💤

1. 접근법

위 문제를 dfs나 bfs로 접근 시, 2^100이라는 경우의 수를 맞을 수 있습니다.

• 현재 위치에서 오른쪽, 아래로 갈 수 있는지 확인
• 갈 수 없다면 패스, 갈 수 있다면 다음 격자의 경우의 수 = 다음 격자의 현재 경우의 수 + 지금 위치의 경우의 수

한 가지 포인트는, 격자를 더해줄 때 1,000,000,007의 나머지 값으로 항상 넣어줘야 한다는 것입니다.

2. 코드

import java.util.*;

class Solution {
    
    static int dirX [] = {1,0};
    static int drrY [] = {0,-1};
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int [][] map = new int [n+2][m+2];
        boolean [][] isWater = new boolean[n+2][m+2];
        
        for(int i=0; i<puddles.length; i++){
            isWater[puddles[i][1]][puddles[i][0]] = true;
        }
        
        map[1][1] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(!isWater[i+1][j]) {
                    map[i+1][j]=(map[i][j]+map[i+1][j])%1000000007;
                }
                if(!isWater[i][j+1]) {
                    map[i][j+1]=(map[i][j]+ map[i][j+1])%1000000007;
                }
            }
        }
        
        return map[n][m]%1000000007;
    }
}

저는 현재 위치에서 다음 위치로 값을 갱신해줬지만, 이전 위치로 현재 위치의 경우의 수를 갱신해주는 방법도 있습니다.

for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == 1 && j == 1) continue;
                if (isWater[i][j]) continue;
                
                map[i][j] = ((map[i-1][j] + map[i][j-1]) % 1000000007);
            }
        }