[프로그래머스, 자바] 등굣길 -동적계획법

프로그래머스 3단계 등굣길 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/42898?language=java

문제설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어질 때, 학교에서 집까지 갈 수 있는 최단경로의 개수를 

1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

격자의 크기 M, N은 1 이상 100 이하인 자연수입니다. 물에 잠긴 지역은 0개 이상 10개 이하입니다. 집과 학교는 물에 잠기지 않았습니다.

입출력 예

m	n	puddles	return
4	3	[[2,2]]	4

자바코드

          
public class Solution {

    public int solution(int m, int n, int[][] puddles) {
        /* 웅덩이 초기화 */
        boolean[][] isPuddles = new boolean[n][m];
        int[][] map = new int[n][m];
        for (int i = 0; i < puddles.length; i++)
            isPuddles[puddles[i][1] - 1][puddles[i][0] - 1] = true;
        
        boolean flag = true;
        for(int i = 0; i < m; i++) { 
        	if(isPuddles[0][i]) flag = false;
        	if(flag) map[0][i] = 1;
        }
        
        flag = true;
        for(int i = 0; i < n; i++) {
        	if(isPuddles[i][0]) flag = false;
        	if(flag) map[i][0] = 1;
        }
        
        for(int i = 1; i < n; i++) 
        	for(int j = 1; j < m; j++) 
        		if(!isPuddles[i][j]) 
        			map[i][j] = (map[i][j - 1] + map[i - 1][j]) % 1000000007;

        return map[n - 1][m - 1];
    }
    
    public static void main(String[] args) {
    	int[][] puddles = {{2, 2}, {3, 2}};
    	System.out.println(new Solution().solution(4, 3, puddles));
    }
}

문제설명

동적게획법 문제이다. 처음 문제를 풀었을 때는 동적계획법과 BFS 탐색을 합쳐서 문제를 풀었다. 지금 짠 코드와 비교하면 굉장히 복잡했다. 

그러나 정확도는 모두 통과했다. 하지만 효율성에서는 모두 틀렸다. 왜 틀렸는지 이해가 되지 않았는데, 효율성 테스트는 굉장히 큰 수에서 테스트했을 것이다.

마지막에 1000000007 로 나누어지지 않았기 때문이었다. 결국은 틀린 풀이는 아니였지만, 좋지 않는 코드였다 

그래서 조금 바꿔보았다. 불필요한 것을 모두 제거하고, 단순하게 작성했다. 이 문제에서 가장 중요한 것은 집을 주변으로 모서리 부분의 값을 모두 초기화하는

작업이다. 집을 기준으로 가로, 세로인 지점에 웅덩이가 없다면 모두 1로 초기화하고, 웅덩이가 존재하면 0으로 초기화해야한다. 

그런 경우는 아래 사진과 같다

위에 사진을 보면 조금 이해하기가 편할 것이다. 길을 찾아가는 방식이 동, 서, 남, 북 모두가 가능할거 같았지만, 실은 우측, 아래 두 방향 뿐이다.

그렇게 생각하면 그렇게 어렵지 않는 문제이다. 근데 동적계획법은 풀이법만 알면 간단히 풀수 있는데, 그 풀이법을 기억해내는 것이 어렵다....

다음 문제는 또 얼마나 어려울까나...