JArchive 프로그래밍 일기

등굣길 문제링크 

리뷰 

최단 경로를 세야 하니까 오른쪽 또는 아래로만 이동해야 한다. 

그래서 특정 지점까지 몇번을 거쳐 가는지 점화식을 세야 한다. 

웅덩이가 있으면 최단경로를 세면 안되니까 처음부터 -1로 초기화 해둔다. 

현재 지점 기준으로 위, 또는 왼쪽의 최단경로를 기반으로  현재 지점의 최단경로를 계산한다. 

인덱스에 음수가 발생하지 않도록 (1, 1)을 시작점으로 두고 (1, 1)의 최단경로를 1로 초기화한다. 

핵심 코드는 아래와 같다

temp_a = (위칸이 음수가 아니라면, ) D[a-1][b] 
temp_b = (왼쪽칸이 음수가 아니라면, ) D[a][b-1] 

D[a][b] = (temp_a + temp_b) % div_num;

맞았습니다 코드 

#include <string>
#include <vector>

using namespace std;
int D[101][101]; // 최단거리를 저장할 배열
int div_num = 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {

  for(auto v : puddles){
    D[v[1]][v[0]] = -1; // 물웅덩이를 -1로 초기화
  }
  D[1][1] = 1;

  for(int i = 1; i <= n; i++){ // n: 행
    for(int j = 1; j <=m; j++){ // m: 열
      if(D[i][j] == -1) continue;
      int temp_a = 0, temp_b = 0;

      if(D[i-1][j] != -1) temp_a = D[i-1][j];
      if(D[i][j-1] != -1) temp_b = D[i][j-1];

      D[i][j] += (temp_a + temp_b) % div_num;
    }
  }

  return D[n][m];
}