[코딩테스트C++] 보행자 천국

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/1832#

보행자 천국

나의 풀이

#include <vector>
#include <iostream>

using namespace std;

int MOD = 20170805;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    
    vector<vector<pair<int, int>>> dp(m, vector<pair<int, int>>(n, make_pair(0, 0)));
    for(int i=1;i<m;i++){
        if(city_map[i][0] == 1){
            break;
        }
        dp[i][0].second = 1;
    }
    for(int i=1;i<n;i++){
        if(city_map[0][i] == 1){
            break;
        }
        dp[0][i].first = 1;
    }
    
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if(city_map[i][j] == 1) // 통행금지
                continue;
            else{
                int left = city_map[i][j-1]; // 좌
                if(left == 2){
                    dp[i][j].first = (dp[i][j].first%MOD + dp[i][j-1].first%MOD);
                }else if(left == 0){
                    dp[i][j].first = (dp[i][j].first%MOD + dp[i][j-1].first%MOD);
                    dp[i][j].first = (dp[i][j].first%MOD + dp[i][j-1].second%MOD);
                }
                
                int up = city_map[i-1][j]; // 상
                if(up == 2){
                    dp[i][j].second = (dp[i][j].second%MOD + dp[i-1][j].second%MOD);
                }else if(up == 0){
                    dp[i][j].second = (dp[i][j].second%MOD + dp[i-1][j].first%MOD);
                    dp[i][j].second = (dp[i][j].second%MOD + dp[i-1][j].second%MOD);
                }
            }
        }
    }

    return (dp[m-1][n-1].first%MOD + dp[m-1][n-1].second%MOD)%MOD;
}

모범 답안

#include <vector>

using namespace std;

int MOD = 20170805;
int M, N;
int DY[] = { 0, 1 };
int DX[] = { 1, 0 };
vector<vector<vector<int>>> cache;

int dfs(int y, int x, int dir, vector<vector<int>>& city_map)
{
  if (y + 1 == N && x + 1 == M)
  {
    return 1;
  }

  int& ret = cache[y][x][dir];
  if (ret != -1)
  {
    return ret;
  }

  ret = 0;
  for (int i = 0; i < 2; i++)
  {
    int dy = y + DY[i];
    int dx = x + DX[i];
    if (dy < 0 || dy >= N || dx < 0 || dx >= M ||
        city_map[dy][dx] == 1 ||
        (city_map[y][x] == 2 && i != dir))
    {
      continue;
    }
    ret = (ret + dfs(dy, dx, i, city_map)) % MOD;
  }
  return ret;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map)
{
  int answer = 0;

  M = n;
  N = m;
  cache.assign(N, vector<vector<int>>(M, vector<int>(2, -1)));
  answer = dfs(0, 0, 0, city_map);

  return answer;
}

배울 점

• 어제 풀어봤던 문제가 약간의 응용만 해서 풀었는데.. 인덱스 하나를 i가 아닌 1로 해놓고 그걸 못찾아서 20분간 삽질했음. ㅋㅋ 제발 이러진 말자

• 저사람은 dfs로 풀었는데 풀수 있는 이유는 갈래길에 따라 결과가 달라지니까. 마지막 칸에 도착한 경우만 1을 반환하니 그것을 모아모아모아오면 정답임
• 오 이것도 좋은 방법이다.