[C언어] 10164. 격자상의 경로

맵의 크기가 작고, 경우의 수가 적아서 그냥 DFS로 풀었다. 근데, 다른 사람들이 0msec이 나오는게 아닌가!!나는 100msec 정도인데...혹시나하고 보니 DP문제였다...ㅎㅎ

O이 주어지면 정답은 :  O까지 가는 경우의 수 * N,M 까지 가는 경우의 수

없으면 N, M까지 가는 경우의 수 이다!!

DFS는 원하는 지점까지 가면, 1을 반환하고 재귀가 종료되면 지금까지 반환 된 값을 반환하는 식으로 구성하였다. 설명하려니까 어렵다. 코드를 보자!!그럼 이해가 될 것이다!!

DP는 비슷하게 반환 된 경우의 수를 DP배열에 저장해 두었고, DP 배열에 이미 경우의 수가 존재하면 현재 저정 된 배열의 값을 반환하는 구성이다.! 역시 글로 쓰자니 어렵다. 코드를 보자!

DFS로 푼 것.

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x;
}point;
 
point Zero;
int map[16][16];
int N, M, O, total;
 
int DFS(int y, int x, int yy, int xx)
{
    if (y > yy || x > xx)
        return 0;
 
    if (y == yy && x == xx)
    {
        return 1;
    }
 
    return DFS(y, x + 1, yy, xx) + DFS(y + 1, x, yy, xx);
}
 
int main()
{
    memset(map, -1, sizeof(map));
    scanf("%d %d %d", &N, &M, &O);
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            map[i][j] = (i - 1)*M + j;
 
            if (map[i][j] == O)
            {
                Zero.y = i;
                Zero.x = j;
            }
        }
    }
 
    if (O == 0)
    {
        total = DFS(1, 1, N, M);
    }
    else
    {
        total = DFS(1, 1, Zero.y, Zero.x) * DFS(Zero.y, Zero.x, N, M);
    }
 
    printf("%d\n", total);
    return 0;
}

DP로 푼 것.

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x;
}point;
 
point Zero;
int map[16][16];
int DP[16][16];
int N, M, O, total;
 
int DFS(int y, int x, int yy, int xx)
{
    if (y > yy || x > xx)
        return 0;
 
    if (DP[y][x])
        return DP[y][x];
 
    if (y == yy && x == xx)
    {
        return 1;
    }
 
    DP[y][x] = DFS(y, x + 1, yy, xx) + DFS(y + 1, x, yy, xx);
 
    return DP[y][x];
}
 
int main()
{
    memset(map, -1, sizeof(map));
    scanf("%d %d %d", &N, &M, &O);
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            map[i][j] = (i - 1)*M + j;
 
            if (map[i][j] == O)
            {
                Zero.y = i;
                Zero.x = j;
            }
        }
    }
 
    if (O == 0)
    {
        total = DFS(1, 1, N, M);
    }
    else
    {
        total = DFS(1, 1, Zero.y, Zero.x) * DFS(Zero.y, Zero.x, N, M);
    }
 
    printf("%d\n", total);
    return 0;
}