프로그래머스 - 등굣길 (C++)

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

프로그래머스

 이번 문제는 주어진 2차원 배열의 왼쪽 위에서 오른쪽 밑까지, 물에 잠긴 곳을 피해 가는 방법은 몇 가지인지를 구하는 문제로, 전형적인 동적계획법(Dynamic Programming) 문제 중 하나라고 생각한다. 진행할 수 있는 방법은 오른쪽, 아래로 두 방향 밖에 없으며, 그렇기 때문에 학교(오른쪽 밑)에서 점점 역으로 진행하며(위, 왼쪽) 가지수를 센다. 이 문제를 풀기 위해 구상한 절차는 다음과 같다.

1. 각 지점마다 가는 방법의 수를 기록하는 변수를 -1로 초기화한다. (-1은 한 번도 검사를 한 적이 없다는 뜻.)
2. 주어진 물에 잠긴 지역의 정보를 따로 저장한다.
3. 재귀 함수를 이용해 답을 구한다. 
   1. 예외 처리를 한다.
      1. 만약 현재 위치가 범위를 벗어난 곳이라면 0을 반환한다. (못 가는 곳이니까, 가는 방법의 수 = 0)
      2. 만약 이미 검사한 곳이라면, 검사해서 나왔던 값을 반환한다.
      3. 만약 물에 잠긴 곳이라면, 원래 못 가는 곳이니까 0을 반환한다.
      4. 만약 집이라면 1을 반환한다.
   2. 현재 위치에 가는 방법을 0으로 초기화한다.
   3. 현재 위치는 현재 위치 기준 왼쪽, 윗쪽에서 올 수 있는 곳이므로, 현재 위치에 오는 방법의 수 = 왼쪽 방법 수 + 윗쪽 방법 수 이다. 

#include <string>
#include <vector>
#include <memory.h>

using namespace std;

#define MAX 101
#define MOD 1000000007

int R, C;                   // 2차원 배열의 행, 열 길이
int visited[MAX][MAX];      // visited[r][c] = 5라면 (r, c)로 가는 방법은 5개라는 뜻.
bool isPuddle[MAX][MAX];    // isPuddle[r][c] == true라면 (r, c)는 물에 잠겼다는 뜻

// 현재 위치가 정해진 범위 안에 있는지를 반환하는 함수
bool IsIn(int r, int c)
{
	return 1 <= r && r <= R && 1 <= c && c <= C;
}

// (r, c) 위치에 도달하는 방법의 수
int Go(int r, int c)
{   
    // 3-1. 예외 처리
    
    // 3-1-1, 만약 현재 위치가 범위를 벗어난 곳이라면 0 반환
    // (못 가는 곳이니까, 가는 방법의 수 = 0)
	if (IsIn(r, c) == false)
		return 0;
    
    // 3-1-2. 만약 이미 검사한 곳이라면, 검사해서 나왔던 값 반환
	if (visited[r][c] >= 0)
		return visited[r][c];
    
    // 3-1-3. 만약 물에 잠긴 곳이라면, 원래 못 가는 곳이니까 0 반환
    if (isPuddle[r][c])
		return 0;
	
    // 3-1-4. 만약 집이라면 1을 반환
	if (r == 1 && c == 1)
		return 1;
    
    // 3-2. 현재 위치에 가는 방법을 0으로 초기화한다.
    visited[r][c] = 0;
    int& dp = visited[r][c];
    
    // 3-3. 현재 위치는 현재 위치 기준 왼쪽, 윗쪽에서 올 수 있는 곳이므로
    // 현재 위치에 오는 방법의 수 = 왼쪽 방법 수 + 윗쪽 방법 수 이다.
    // 그리고 MOD는 문제에서 1,000,000,007로 나눈 나머지를 return 하라고 하였기 때문에 계산해 준 것.
	dp += ((Go(r - 1, c) + Go(r, c - 1)) % MOD);
    
    return dp;
}

int solution(int m, int n, vector<vector<int>> puddles)
{
	R = n;
	C = m;
    
    // 1. 각 지점마다 가는 방법의 수를 기록하는 변수를 -1로 초기화한다.
    // -1은 한 번도 검사를 한 적이 없다는 뜻.
	for (int r = 0; r < MAX; ++r)
	{
		for (int c = 0; c < MAX; ++c)
        {
            visited[r][c] = -1;
        }
	}
    
    // 2. 주어진 물에 잠긴 지역의 정보를 따로 저장한다.
	for (int i = 0; i < puddles.size(); ++i)
	{
		vector<int> puddle = puddles[i];	
		int puddleR = puddle[1];
		int puddleC = puddle[0];

		isPuddle[puddleR][puddleC] = true;
	}
    
    // 3. 재귀 함수를 이용해 답을 구한다. 
	int answer = Go(R, C);

	return answer;
}