[백준 1520] - 내리막길(C++)[골드3]

문제

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

1520번: 내리막 길

 

🔎문제 설명

 

문제만 보고 이게 DP문제인가? 싶었다.

그냥 무작정 BFS를 사용해서 풀었다.

그랬더니 시간초과가 났다.

이동하는 조건만 맞으면 큐에 넣어줬고, 

도착지점에 도착한다면 그게 적절한 이동이라고 생각해서, 결괏값을 계속 더해줘서

함수를 탈출한다면 결과값을 출력해 줬지만 아마 배열 크기도 크고, 큐에 쓸데없는 없는 값이 많이 들어가서 그런 거 같다.

 

다른 사람들의 풀이를 보니 dfs를 쓴 풀이가 많았지만, 꾸역꾸역 bfs로 풀고 싶었다.

 

그래서 기존 큐가 아닌 우선순위 큐를 사용해서 풀었다.

 

우선순위 큐를 사용해서 큐에 넣을 원소들을 미리 걸러주는 작업을 하니 시간초과가 해결되었다.

큐에 여러번 원소를 넣지 않아도 되니 여러 번 이동하는 작업도 줄어들었다.

pq값은 항상 높이를 내림차순으로 정렬해줬다.

 

2번째, 3번째 경로에서 우리는 20을 중복해서 방문하는 것을 알 수 있다.

이러한 경우 따로 걸러주는 작업을 하지 않으면, 20이 큐에 여러 번 들어가는 불필요한 작업이 들어가게 된다.

계속 높이가 큰 값을 기준으로 큐를 탐색하다가, 해당 배열에 경로 값이 0이라면 큐에 넣어주고, DP값을 더해주고,

경로 값이 0이 아니라면 해당 원소에 대해서 이미 탐색했다는 뜻이므로, DP값만 업데이트해줬다.

여러 번 반복하는 경우는 이렇게 값만 업데이트해주면 된다.

🔎전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m;
vector<vector<int> >road;
struct cmp{
    bool operator()(pair<int,pair<int,int> >&a,pair<int,pair<int,int> >&b){
        return a.first<b.first;
    }
};
priority_queue< pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,cmp>  pq;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int dp[501][501]={0};
void bfs(){
    pq.push(make_pair(road[0][0],make_pair(0,0)));
    dp[0][0]=1;
    while(!pq.empty()){
        int row= pq.top().second.first,col=pq.top().second.second;
        pq.pop();
        for(int i=0; i<4; i++){
            int trow=row+dir[i][0], tcol= col+dir[i][1];
            if(trow<0 || tcol<0 || trow>=n || tcol>=m){
                continue;
            }
            if(road[row][col]>road[trow][tcol]) //높이가 더 낮은 지점으로만 이동함.
            {
                if(dp[trow][tcol]==0) //첫 방문이라면 pq에 넣음.
                {
                    pq.push(make_pair(road[trow][tcol],make_pair(trow,tcol)));
                }                               
                dp[trow][tcol]+=dp[row][col];
            }
        }
    }
}
int main(){
    cin>>n>>m;
    road.resize(n,vector<int>(m,0));
    for(int i=0; i<n; i++){
        for(int j=0; j<m;j++){
            cin>>road[i][j];
        }
    }
    bfs();
    cout<<dp[n-1][m-1]<<endl;
}

 

😀느낀 점

• 우선순위 큐를 사용할 때마다 선언에서 애를 먹었다.
• 구조체로 선언하는 방법도 있는데, 정말 익숙하지가 않네..
• 비교하는 구조체인 cmp를 생성하는 것도 여러 번 써봐야 할 것 같다.