(1520) 내리막 길

https://www.acmicpc.net/problem/1520

단계별로 풀어보기

31단계(동적 계획법 2) 3번째

 

 

 

DP와 그래프 순회(BFS, DFS)를 결합한 문제.

음... 잘 모르겠다. 개인적으로 이전 문제에 비하면 방법을 떠올리기도 어렵지 않았고 구현도 그리 어렵지 않았다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int,int> p;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int m, n;
  
  cin >> m >> n;
  
  vector v(m, vector<int> (n)), dp= v;
  priority_queue<p> pq;
  
  for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
      cin >> v[i][j];
    }
  }
  
  dp[0][0]= 1;
  pq.push({v[0][0], 0});
  
  while(!pq.empty()){
    int nowx= pq.top().second/n;
    int nowy= pq.top().second%n;
    int nowh= pq.top().first;
    pq.pop();
    
    for(int i=0;i<4;i++){
      int nextx= nowx+"0121"[i]-'1';
      int nexty= nowy+"1012"[i]-'1';
      
      if(nextx<0 || nextx>m-1 || nexty<0 || nexty>n-1)  continue;
      if(nowh<=v[nextx][nexty])  continue;
      
      if(!dp[nextx][nexty])  pq.push({v[nextx][nexty], nextx*n+nexty});
      dp[nextx][nexty]+= dp[nowx][nowy];
    }
  }
  
  cout << dp[m-1][n-1];
  
  return 0;
}