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

프로그래머스 42898 - 등굣길

문제 링크

생각 및 접근

• 초중고 시절 많이 했던 최단거리 구하기 문제를 코딩으로 구현하게 될 줄 몰랐다.
• 최단거리 문제에 대한 정보는 깔끔수학님의 블로그를 참고하자.
• 인덱스 생각 때문에 애먹었는데, 좌표와 행렬 표현의 이질적인 부분 때문이다.

  • 

  • 행렬로 생각하면 집이 [1][1], 학교는 [3][4]여야 하는데,
  • 좌표로 따지면 집이 (1, 1)이라고 하면, 학교의 좌표는 (4, 3)이다.
  • 좌표로 표현한 것들을 행렬로 바꾸려면 x와 y값을 뒤집어주어야 한다!
  • 어떻게 할까 고민하다가, 행렬을 기준으로 생각해서, 좌표인 것들을 뒤집어주기로 했다.
• 좌표를 행렬로 바꾸기
  • 행렬 dp에서 PUDDLE를 넣을 때,

      for(auto k : puddles)   dp[k[1]][k[0]] = PUDDLE;

    와 같이 하였다.
  • 행렬 dp의 첫번째 인덱스의 끝은 m, 행렬 dp의 두번째 인덱스의 끝은 n으로 하였다.
  • solution 함수의 반환값 또한 dp[n][m]
• dp의 초깃값 잡기

    for(auto k : puddles)   dp[k[1]][k[0]] = PUDDLE;
    for(int i = 1; i <= m; i++){
        if(dp[1][i] == PUDDLE)  break;
        dp[1][i] = 1;
    }
    for(int i = 1; i <= n; i ++){
        if(dp[i][1] == PUDDLE)  break;
        dp[i][1] = 1;
    }

• dp 계산

    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            if(dp[i][j] == PUDDLE)  continue;
            if(dp[i - 1][j] != PUDDLE)  dp[i][j] += dp[i - 1][j];
            if(dp[i][j - 1] != PUDDLE)  dp[i][j] += dp[i][j - 1];
            dp[i][j] %= 1000000007;
        }
    }

코드

#include <bits/stdc++.h>
#define PUDDLE -1
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector< vector<int> > dp(n + 1, vector<int>(m + 1, 0));
    for(auto k : puddles)   dp[k[1]][k[0]] = PUDDLE;
    for(int i = 1; i <= m; i++){
        if(dp[1][i] == PUDDLE)  break;
        dp[1][i] = 1;
    }
    for(int i = 1; i <= n; i ++){
        if(dp[i][1] == PUDDLE)  break;
        dp[i][1] = 1;
    }

    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            if(dp[i][j] == PUDDLE)  continue;
            if(dp[i - 1][j] != PUDDLE)  dp[i][j] += dp[i - 1][j];
            if(dp[i][j - 1] != PUDDLE)  dp[i][j] += dp[i][j - 1];
            dp[i][j] %= 1000000007;
        }
    }

    return dp[n][m];
}

채점 결과