[백준 1520] 내리막 길 / C++

1520번: 내리막 길 (acmicpc.net)]

1520번: 내리막 길

 

문제 이해

1. 세준이는 좌표평면 (0, 0) 에서 (n-1, m-1)까지 가는 경우의 수를 구해야 한다.

2. 세준이는 자신이 있는 곳의 높이보다 작은 높이인 좌표로 이동가능 하다.

    2-1. 높이가 낮은 곳이 아니면 이동 못하다.(높이가 같은 곳도 이동 못함)

 

기본 아이디어 : 최단 거리로 이동하는 경우의 수

그냥 중고등학교 때 경우의 수 문제 풀면서 보는 기초 문제이다.

이것을 보면 이해가 될 것 이다.

경우의 수와 확률 ; 최단 거리 문제 : 네이버 블로그 (naver.com)

경우의 수와 확률 ; 최단 거리 문제

 

이에서 사용된 아이디어인 (0, 0)에서 (0, 1)와 (1, 0)을 갈 수 있으니 각 좌표에다 +1을 한다 라는 로직을 쓸 것이다.

우리는 (0, 0)좌표에다가 가중치 1을 기억시키고 (0, 0)이 갈 수 있는 곳에다 (0, 0)의 가중치 1을 더하는 형식으로 연산하면 될 것 이다.

연산을 한 좌표 당 한 번을 하는 것이 중요하다.

 

아이디어 1 : 위상정렬

나는 이 문제를 완전히 이해하고 나서 '가장 높은 곳에서 부터 차례로 연산하면 어떻게 될까?' 라는 생각을 하게되었다.

 

이 문제의 조건에 따르면 3가지 경우가 나온다.

  1. (x1, y1)  에서  (x2, y2) 로 이동할 수 있다

  2. (x2, y2)  에서  (x1, y1) 로 이동할 수 있다.

  3. (x1, y1)와 (x2, y2)는 서로 이동 못한다.

 

이를 통해 양방향으로 이동할 수 있는 경우가 없다는 것을 알 수 있었다. --> 위상정렬 사용가능

가장 높은 좌표일 경우로 진입할 수 없다는 것을 통해 이 좌표는 연산을 이어가도 또 다시 연산을 하지는 않을 것이다.

 

연산 과정

  1. 가장 높은 좌표를 찾는다. (우선 순위 큐 사용)

  2. 가장 높은 좌표의 가중치 이동할 수 있는 좌표에 더한다.

  3. 연산 한 좌표는 제외 시킨다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int h[510][510];
long long int p[510][510];
int x2[4]={1, -1, 0, 0};
int y2[4]={0, 0, 1, -1};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m; cin>>n>>m;

    priority_queue<pair<int, pair<int, int> > > H;

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>h[i][j];
            H.push({h[i][j], {i, j}});
        }
    }

    p[0][0]=1;

    while(!H.empty())
    {
        int x, y;
        long long int h2;

        h2=H.top().first;
        x=H.top().second.first;
        y=H.top().second.second;
        H.pop();

        if(p[x][y]==0) continue;

        for(int i=0; i<4; i++)
        {
            int X=x+x2[i], Y=y+y2[i];

            if(!(0<=X && X<n) || !(0<=Y && Y<m)) continue;
            if(h[X][Y]<h2) p[X][Y]+=p[x][y];
        }
    }

    cout<<p[n-1][m-1];

    return 0;
}

 

장점 : 구현이 쉽다.

단점 : 메모리가 많이 먹힌다...

 

아이디어 2 : DP+DFS

일단 (n-1, m-1) 좌표에다 가중치 1을 더하고 (n-1, m-1)로 갈 수 있는 인접한 좌표에 가중치를 더하면 되는 간단한 BFS 아이디어를 사용할 것 이다.

기존 BFS로는 (2, 3)에서 (n-1, m-1)로 가는 방법을 한번 연산을 했어도 (2, 3)으로 가는 방법을 다시 연산해야한다.

 

하지만 DP를 사용한다면 어떠한 좌표에서 (n-1, m-1)로 가는 경우의 수를 알고 있다면 그것을 기억시키다면 위 같은 연산을 반복 하지 않아도 된다는 것이다.

위같은 경우는 (1, 1)은 (1, 0)와 (0, 1)에서 들어갈 수 있다.

(1, 1)에서 (2, 2)로 갈 수 있는 경우는 1가지이다. 이를 기억을 시킨다음에 (1, 0)와 (0, 1)에 1를 더하면 되는 것이다,

 

연산과정(재귀)

  1. (0, 0)에서 재귀를 돌린다.

  2. 갈 수 있는 좌표로 이동한다.

  3. 만약 (n-1, m-1)좌표에 도착을 했다면 들어 갔었던 좌표에 가중치 1을 더하고 리턴시킨다,

  4. 어떠한 좌표에서의 연산이 끝난다면 그 좌표에 들어 갔다는 체크를 하고 그 좌표의 가중치를 리턴시킨고 이를 더한다.

 

코드(재귀)

#include <bits/stdc++.h>
using namespace std;

bool f[510][510]; int n, m;
int h[510][510];
long long int p[510][510];

int x2[4]={1, -1, 0, 0};
int y2[4]={0, 0, 1, -1};

long long int dp(int x, int y)
{
    long long int P=0;

    if(f[x][y]) return p[x][y];

    f[x][y]=1;

    for(int i=0; i<4; i++)
    {
        int X=x+x2[i], Y=y+y2[i];

        if(!(0<=X && X<n) || !(0<=Y && Y<m)) continue;
        if(h[x][y]<=h[X][Y]) continue;
        P+=dp(X, Y);
    }

    p[x][y]=P;
    return P;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>n>>m;

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>h[i][j];

    f[n-1][m-1]=1; p[n-1][m-1]=1;

    cout<<dp(0, 0);

    return 0;
}

 

  코드 평 : 정석 그 자체 / BFS DP를 모른다면 떠오르지 안는 코드이다. (나도 그럼)

 

 

 

문제 평

 BFS + DP 의 정석과 같은 문제인 것 같다. 무조건적으로 풀어야하는 문제라고 여겨진다.