[Algorithm]Baekjoon 10164번 :: 격자상의 경로

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

10164번: 격자상의 경로

 
 
struct Node
{
    int y;
    int x;
};
 
int n, m, k;
int arr[16][16] = { 0 };
int dirs[2][2] = { {0,1}, {1,0} };
int circleY = 0;
int circleX = 0;
 
int BFS(Node start, Node dest)
{
    queue<Node> q;
    q.push({ start.y, start.x });
    int count = 0;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        if (curY == dest.y && curX == dest.x)
        {
            ++count;
            continue;
        }
        
        for (int i = 0; i < 2; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (nextY > dest.y) continue;
            if (nextX > dest.x) continue;
 
            q.push({ nextY,nextX });
        }
    }
 
    return count;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m >> k;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            arr[i][j] = (i * m + j) + 1;
        }
    }
 
    --k;
    if (k == -1)
    {
        cout << BFS({ 0,0 }, { n - 1,m - 1 });
    }
    else
    {
        circleY = k / m;
        circleX = k % m;
 
        cout << BFS({ 0,0 }, { circleY,circleX }) * BFS({ circleY,circleX }, { n - 1,m - 1 });
    }
}

 

dp카테고리의 문제를 풀던 중에 풀었던 문제로, 일단 위의코드는 그냥 아무생각없이 탐색으로 푼 문제이다.

n,m값이 작아서 그냥 탐색으로 되겠거니 하고 푼 건데, 통과는 했다. 다만 생각보다 수행속도가 높게 나왔다.(400ms대)

가만 생각해보니 n,m값이 최대 15이더라도, 굉장히 탐색횟수가 많아질 수 있을만하다고 생각했다.

 

애초에 dp카테고리문제기도하고, 가만보니 굳이 탐색으로할 필요가 없어서 다시 생각해서 풀었다.

특정칸 i,j까지의 경로의 수는, [i-1][j]의 경로의 수와 [i][j-1]의 경로의 수의 합인것을 알아냈고, 그러면 시간복잡도를 (n + m + n*m)으로 줄일 수 있다.

 

 
 
int n, m, k;
int circleY = 0;
int circleX = 0;
int dp[15][15] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> k;
 
    --k;
    circleY = k / m;
    circleX = k % m;
 
    for (int i = 1; i < n; ++i)
    {
        dp[i][0] = 1;
    }
 
    for (int i = 1; i < m; ++i)
    {
        dp[0][i] = 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 (k == -1)
    {
        cout << dp[n - 1][m - 1];
    }
    else
    {
        cout << dp[circleY][circleX] * dp[n - 1 - circleY][m - 1 - circleX];
    }
}
 

 

주어진 격자의 각 첫번째 행과 열을 1로 초기화 후, 1,1부터 n-1,m-1까지 dp테이블을 업데이트했다.

동그라미가 없으면 그냥 dp[n-1][m-1]을 출력하면 되고, 있을 경우 동그라미까지의 경로의 값과 동그라미부터 n-1,m-1까지의 경로의 값을 곱해주면 된다.

 

동그라미부터 n-1,m-1까지의 경로는 곧 0,0부터 n-1-circleY, m-1-circleX와 동일하다.

현재 dp테이블은 0,0을 기준으로 각 칸에 대해 경로의수가 업데이트 되어있기 때문에, 동그라미부터 n-1,m-1까지의 경로를 구하기위해 dp테이블을 이용하려면 0,0으로 매핑시켜야 한다.

그렇기 때문에 dp[n-1-circleY][m-1-circleX] 로 표현해야 한다.