백준 1520번 내리막 길

🔒[문제 url]

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

🔑알고리즘

목적지까지의 모든 경로를 탐색해야한다? DFS
지도의 크기가 클 경우, 완전탐색은 시간초과를 야기하므로 DP를 적용한다.

• visited 이차원 배열을 선언하여,vistied[x][y] 에 map[x][y] 까지의 경로 갯수를 저장한다. 또한, -1로 초기화하고 0으로 갱신하여 방문 기록을 처리한다.
  • 반복되는 부분 문제를 해결하는 DP 역할 배열
  • 방문 기록을 처리해준다.
    
    
• map[x][y] 지점까지의 경로 갯수는 어떻게 구하는가?
  • (상, 하, 좌, 우) 네 방향 중 현재 지점으로 올 수 있는 지점. 즉, 현재 지점보다 더 높은 곳들까지의 경로 갯수의 합이다.
    • 주변 지점의 visited[x][y] 값이 -1 이라면, DFS 탐색을 진행한 후 더해준다.
    • visited[x][y] > 0 , 즉 이미 탐색이 진행된 지점이라면 값을 그대로 더해준다.

🐾부분 코드

int DFS(int x, int y)
{
    if (x == n && y == m) return 1;
    else if (visited[x][y] != -1) return visited[x][y];

    visited[x][y] = 0; // 방문 처리

    int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; // 상 우 하 좌
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (1 <= nx && nx <= n && 1 <= ny && ny <= m)
        {// 범위 체크
            if (map[x][y] > map[nx][ny])
            {// 내리막길이라면
                visited[x][y] += DFS(nx, ny);
            }
        }
        
    }
    return visited[x][y];
}

<DFS 함수>
DFS 탐색 및 DP 갱신 함수이다.
위에서 설명한 알고리즘에 따라, 동서남북 네 방향 중 내리막길이 성립되는 지점에 대하여 DFS 탐색을 진행한다. 이때, 탐색할 지점visited[nx][ny]에 대해 값이 갱신되어있다면 그대로 return하여 더해준다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
#include <cmath>
using namespace std;

int n, m;
int map[501][501];
int visited[501][501]; // dp역할 : [x][y]까지의 경로 갯수

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> map[i][j];
            // -1로 초기화하고 0으로 갱신해 방문기록 처리
            visited[i][j] = -1;
        }

}

int DFS(int x, int y)
{
    if (x == n && y == m) return 1;
    else if (visited[x][y] != -1) return visited[x][y];

    visited[x][y] = 0; // 방문 처리

    int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; // 상 우 하 좌
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (1 <= nx && nx <= n && 1 <= ny && ny <= m)
        {// 범위 체크
            if (map[x][y] > map[nx][ny])
            {// 내리막길이라면
                visited[x][y] += DFS(nx, ny);
            }
        }
        
    }
    return visited[x][y];
}

void SOLVE()
{
    cout << DFS(1, 1);
}


int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

-1로 초기화를 안 해줘도, 어차피 다 0 이상이니까 굳이 안 해줘도 되는거 아니야?
라고 생각했다가 시간 초과를 받은 문제이다. 방문을 했는지 안 했는지 판별을 못 한다는 것은 재귀를 훨씬 더 많이 반복하게 되기때문에 다시금 기본기를 다잡게 된 문제이다.