CPP19

JUSTICE_DER·2023년 8월 25일

⏲ CPP - 코딩테스트

목록 보기

24/41

1. 1520 - DFS / DP

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

DFS로 풀어야 할 것 같다는 생각이 들었다.
DP문제라고 보았는데, DP를 왜 쓸까 생각도 들었다.

그냥 목표점에 도달하면 count를 세고,
출력만 하면 되는게 아닌가??

일단 해본다.

시도

#include <iostream>
using namespace std;

int cx[4] = {1, 0, -1, 0};
int cy[4] = {0, -1, 0, 1};

void DFS(int, int);

int map[501][501];
int M, N;

int count = 0;

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

    cin >> N >> M; // 세로 가로 - 가로 세로로 쓸 예정

    /* 0으로 초기화
    for (int i = 0; i < N; i++)
    {
        fill(&map, &map+500, 0);
    }
    */

    // 입력
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }

    DFS(0, 0);

    cout << count;

    return 0;
}

void DFS(int x, int y)
{
    if (x == N - 1 && y == M - 1)
    {
        count++;
    }

    for (int i = 0; i < 4; i++)
    {
        int dx = x + cx[i];
        int dy = y + cy[i];

        if (dx < 0 || dy < 0 || N < dx || M < dy)
        {
            continue;
        }
        else
        {
            if (map[dx][dy] < map[x][y]) // 내리막길이라면
            {
                DFS(dx, dy);
            }
        }
    }
}

DFS로 구현했는데.. 음
시간초과가 났다.

역시 카테고리에 맞게 DP를 사용해야만 하는건가
사용한다면 어떻게?

특정 좌표를 방문할 때마다 map크기의 dp에 표시를 해야하나?
표시를 한다고 뭐가 달라지나? 오히려 그냥 도착하면
count 변수 하나만 증가시키는게 효율적인 것 같은데?

갔던 DFS경로를 탐색하지 않도록 막는 방식으로
DFS횟수를 제한하도록 DP를 작성해야만 의미가 있는 것 같은데..
음.. 어떻게..?
어떻게 탐색하지 않고도 목적지가 아닌걸 알고 막을까?

가장 첫 DFS 경로를 구해버리고
그 다음 DFS가
해당 경로 내에 존재하는 좌표중 하나라도 갔다면 무조건
도착지까지 갈 수 있으므로 생략하는 방식을 쓸까?

시도 2

#include <iostream>
#include <vector>
using namespace std;

int cx[4] = {1, 0, -1, 0};
int cy[4] = {0, -1, 0, 1};

int DFS(int, int);

int map[501][501];
int d[501][501];    // DP
int M, N;

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

    cin >> N >> M;

    // 입력
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
            d[i][j] = -1; // d -1로 초기화
        }
    }

    cout << DFS(0, 0);
    return 0;
}

// 목적지가 아니라면 최종적으로 d[x][y]를 반환한다.
int DFS(int x, int y)
{
    if (x == N - 1 && y == M - 1)
    {
        return 1;
    }

    if (d[x][y] == -1)  // 한번도 방문한 적이 없다면,
    {
        d[x][y] = 0;    // 방문 표시를 한다
        for (int i = 0; i < 4; i++)
        {
            int dx = x + cx[i];
            int dy = y + cy[i];

            if (dx < 0 || dy < 0 || N <= dx || M <= dy)
            {
                continue;
            }
            else
            {
                if (map[dx][dy] < map[x][y]) // 내리막길이라면
                {
                    d[x][y] += DFS(dx, dy); // d(dxdy)값을 d(xy)에 더함
                }
            }
        }
    }
    return d[x][y];
}