[백준] 1520 - 내리막 길

1. 문제

1520번: 내리막 길

2. 개요

각 위치의 높이가 쓰여진 M x N 크기의 지도가 주어진다.

이동은 해당 칸보다 낮은 높이의 상하좌우로만 이동할 수 있다.

제일 왼쪽 위에서 제일 오른쪽 아래로 갈 수 있는 경우의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

처음엔 그냥 DFS로 풀어봤으나 당연히? 시간초과였다.

경로의 수를 찾는 문제라 visited를 통해 중복을 걸러내는 작업을 할 수가 없고,

모든 길에 대한 탐색을 진행하다보니 시간초과가 뜨는 게 아닐까 싶다.

---

DP 테이블을 따로 작성해 -1로 초기화한다. 이제 방문할 수 없는 지역을 -1로 판단하게 된다.

방문했는데 현 위치의 dp값이 -1이라면 0으로 다시 초기화해준다.

-1이 아니라면 이미 방문 했던 곳이므로 그 값만큼 해당 위치에 더해준다.

도착점에 도착했다면 1를 작성한다.

위 작업을 재귀로 돌리고 작업이 끝났으면 시작점의 dp값을 출력한다.

3-2. Python - 시간 초과

import sys
sys.setrecursionlimit(10000000)
M, N = map(int, sys.stdin.readline().split())

board = []
visited = [[0 for i in range(N)] for j in range(M)]
for i in range(M):
    board.append(list(map(int, sys.stdin.readline().split())))

dirY, dirX = [-1, 0, 1, 0], [0, 1, 0, -1]
visited[0][0] = 1

def dfs(y = 0, x = 0):
    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY >= M or nextY < 0 or nextX >= N or nextX < 0:
            continue
        if board[nextY][nextX] >= board[y][x]:
            continue
        
        visited[nextY][nextX] += 1
        dfs(nextY, nextX)

dfs()
print(visited[-1][-1])

3-3. Python

import sys
sys.setrecursionlimit(1000000000)
M, N = map(int, sys.stdin.readline().split())

board = []
for i in range(M):
    board.append(list(map(int, sys.stdin.readline().split())))

dp = [[-1 for i in range(N)] for j in range(M)]

dirY, dirX = [-1, 0, 1, 0], [0, 1, 0, -1]

def dfs(y = 0, x = 0):
    if y == M-1 and x == N-1:
        return 1

    if dp[y][x] != -1:
        return dp[y][x]

    else:
        dp[y][x] = 0

        for i in range(4):
            nextY, nextX = y + dirY[i], x + dirX[i]

            if nextY >= M or nextY < 0 or nextX >= N or nextX < 0:
                continue
            if board[nextY][nextX] >= board[y][x]:
                continue
            
            dp[y][x] += dfs(nextY, nextX)

        return dp[y][x]

dfs()

print(dp[0][0])

3-4. C#

class Program
{
    static int M;
    static int N;
    static int[,] dp;
    static int[,] table;

    static int[] dirY = { -1, 0, 1, 0 };
    static int[] dirX = { 0, -1, 0, 1 };

    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int _M = int.Parse(input[0]);
        int _N = int.Parse(input[1]);

        M = _M;
        N = _N;

        dp = new int[M, N];

        table = new int[M, N];

        for (int i = 0; i < M; i++)
        {
            string[] row = Console.ReadLine().Split();
            for (int j = 0; j < N; j++)
            {
                table[i, j] = int.Parse(row[j]);
                dp[i, j] = -1;
            }
        }

        DFS();

        Console.WriteLine(dp[0, 0]);
    }

    static int DFS(int y = 0, int x = 0)
    {
        if (y == M - 1 && x == N - 1)
            return 1;

        if (dp[y, x] != -1)
            return dp[y, x];

        else
        {
            dp[y, x] = 0;
            for (int i = 0; i < 4; i++)
            {
                int nextY = y + dirY[i];
                int nextX = x + dirX[i];

                if (nextY < 0 || nextY >= M || nextX < 0 || nextX >= N)
                    continue;
                if (table[y, x] <= table[nextY, nextX])
                    continue;

                dp[y, x] += DFS(nextY, nextX);
            }
            return dp[y, x];
        }
    }
}