백준 10164번: 격자상의 경로

백준 10164번: 격자상의 경로

10164번: 격자상의 경로

 

가장 좌측 상단에서 가장 우측 하단으로 내려올 때 O를 거쳐온 곳의 경로의 수를 구하는 문제이다. 문제를 하나 이해를 제대로 하지 않아 틀렸던 문제이다. 나는 O가 없는 경우에는 가는 방법이 없다고 착각을 했었다. O가 없는 경우에는 모든 경로의 수가 정답이다.

나는 보자마자 DFS로 풀어야겠다! 해서 DFS와 DP를 이용하여 문제를 해결했는데 나중에 보니 더욱 더 간단한 방법이 있었다는 것을 알게되었다. 간단한 방법에 대해서 이야기하자면 좌측상단에서 우측하단으로 이동할 수 있는 모든 경로의 수를 구해놓고

좌측상단에서 O까지 가는 경로의 수 * O부터 우측하단까지 가는 경로의 수 = O를 지나쳐 목적지점까지가는 경로의수

를 하면 dfs를 쓰는것보다 훨씬 쉽게 답을 구할 수 있다.

dfs도 틀린 것은 아니니 두 개 다 소스코드를 올리겠다.

 

1. DFS + DP를 이용한 방법

#include <iostream>
#include <cstring>
using namespace std;
int n, m, k;
int limitY, limitX;
int field[16][16];
int dp[16][16];
int dirY[] = {0,-1};
int dirX[] = {-1,0};

int dfs(int y, int x, bool isK)
{
    int dy, dx;
    if(y == limitY && x == limitX)
        isK = true;
    if(dp[y][x] != 0) return dp[y][x];
    if(y == 0 && x == 0)
    {
        dp[y][x] = 1;
        return 1;
    }
    for(int i = 0; i < 2; i++)
    {
        dy = y + dirY[i];
        dx = x + dirX[i];
        if(isK){
            if(dy < 0 || dx < 0) continue;
        }
        else{
            if(dy < limitY || dx < limitX) continue;
        }
            
        dp[y][x] += dfs(dy, dx, isK);
        
    }

    return dp[y][x];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    int num = 1;
    //1~n*m 초기화
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(num == k)
            {
                limitY = i;
                limitX = j;
            }
            field[i][j] = num++;
        }
    }
    memset(dp, 0, sizeof(dp));
    dfs(n-1, m-1, false);
    cout << dp[n-1][m-1];
    return 0;
}

2. Only DP

#include <iostream>
#include <cstring>
using namespace std;
int n, m, k;
int field[16][16];
int dp[16][16];



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    int ky, kx;
    int num = 1;
    //1~n*m 초기화
    dp[0][1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
            if(num++ == k){
                ky = i;
                kx = j;
            }
        }
    }
    if(k == 0)
    {
        cout << dp[n][m];
        return 0;
    }
    int my = n - ky + 1;
    int mx = m - kx + 1;
    cout << dp[ky][kx] * dp[my][mx];
    return 0;
}

 

후자가 더욱 더 효율적이다.