이문제의 핵심은 도달 가능한 지점의 개수 = 왼쪽개수 + 위쪽개수 가 핵심

 1(1,1) 1(1,2)
 1(2,1) 2(2,2)

그리드에서 (2,2) 위치 도달 개수는

왼쪽(2,1) 도달개수 1
위쪽(1,2) 도달개수 1
도착지점의 도달 개수는 결국 왼쪽에서 들어오는 길, 위쪽에서 들어 오는길 2가지 이므로
결국 왼쪽+위쪽 의 개수가 된다.
웅덩이는 지나갈 수 없으므로 0이 되는 것

점화식으로 표현하면

point(n. m) = point(n, m -1) + point(n-1, m)

해결책

그리드 배열의 인덱스는 0 부터 이나, 문제에서는 1 부터 이므로 배열[n+1][m+1] 선언한다.
웅덩이는 선언된 그리드 배열에 -1 값으로 표시한다(처리 시 0은 아직 개수가 계산되지 않은 지점, -1은 웅덩이를 구별하기 위함)
출발 지점 그리드[1][1] = 1로 설정한다.
재귀를 사용하여 점화식을 그대로 표현 하여 구현한다.
재귀에서 이미 point(1,1) 보다 이전 위치의 값은 은 0을 리턴, 처리된 값이 있다면 그값을 리턴, 웅덩이라면 0을 리턴 하도록 처리

주의

웅덩이 배열 값 [1,2] => [row, col] 이 아니라 반대 입니다. 이것 때문에 로직은 맞으나 테스트를 통과 못하여 한참을 찾았네요..ㅠ
즉 그리드에 웅덩이 값을 선언 할때 grid[2][1] = -1 이렇게 들어 가야합니다.

작성중인 코드―Solution.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Arrays;

class Solution {
    private static int[][] matrix;

    public static int solution(int m, int n, int[][] puddles) {
        matrix = new int[n+1][m+1];
        Arrays.stream(puddles).forEach(v -> matrix[v[1]][v[0]] = -1);
        matrix[1][1] = 1;
        return recursive(n,m);
    }

    private static int recursive(int row, int col) {
        if (row < 1 || col < 1 || matrix[row][col] < 0) return 0;
        if (matrix[row][col] > 0) return matrix[row][col];
        return matrix[row][col] = (recursive(row, col - 1) + recursive(row - 1, col)) % 1000000007;
    }
}

Answer 1

출발		1
1		1
x		1
	1	1	o	1
				1	도착

1 -> 웅덩이

18***

2020.1.5 18:42

재귀를 사용하여 해결하는 방법

이문제의 핵심은 도달 가능한 지점의 개수 = 왼쪽개수 + 위쪽개수 가 핵심

점화식으로 표현하면

해결책

주의

작성중인 코드―Solution.java

1 개의 답변

45***

2020.2.8 05:45

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.