프로그래머스 : 등굣길

https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=3%2C4%2C5&languages=java

코딩테스트 연습 | 프로그래머스 스쿨

구해야할 것

등굣길의 가짓수 -> 문제 훑고 최단거리라고 착각하지 말자. 그렇다면 DFS를  쓸 이유도, DP를 사용할 이유도 없다.

 

접근 방법

얼핏 보면 DFS/BFS문제 같다.

이 문제는 경로의 가짓수이므로 BFS를 제외한다.

 

BFS를 제외한다면, 분명하게 DFS이다. 

그렇지만 여기서 나는 1000000007로 나누라는 불안한 조건을 보았고,

DP로 꺾었다.

(근데 어차피 이 흐름 없어도 문제의 최상단에는 DP라고 떡 박혀있긴 하다)

 

관건은 DP를 어떻게 적용할 것인가?

이건 굉장히 간단한데, 결국 어떤 (row,col)에서 경로의 가짓수는 오른쪽과 아래쪽으로밖에 갈 수 없다는 문제의 조건 상 (row-1,col)+(row,col-1)일 수밖에 없다.

 

이걸 이중 for문으로 사용한다면 memoization을 채워나가면 끝

 

아래는 코드 전문이다.

import java.util.*;
import java.awt.*;

class Solution {
    private static int answer;
    private static boolean[][] hazards;
    
    private static int[][] memo;

    public int solution(int m, int n, int[][] puddles) {
        answer = 0;
        hazards=new boolean[n][m];
        memo=new int[n][m];
        
        for(int[] puddle:puddles){
            hazards[puddle[1]-1][puddle[0]-1]=true;
        }
        
        for(int row=0;row<n;row++){
            for(int col=0;col<m;col++){
                if(row==0&&col==0){
                    memo[row][col]=1;
                } else if(row==0&&!hazards[row][col]){
                    memo[row][col]+=memo[0][col-1]%1000000007;
                } else if(col==0&&!hazards[row][col]){
                    memo[row][col]+=memo[row-1][0]%1000000007;
                } else if(!hazards[row][col]){
                    memo[row][col]=(memo[row-1][col]+memo[row][col-1])%1000000007;
                }
            }
        } 
        return memo[n-1][m-1]%1000000007;
    }
}

 

문제 후기

그지같은 문제다. 

(행,열)이라는 Streotype을 버리고 (열,행)으로 조건을 줘서 사람을 헷갈리게 만드냐