[BOJ][C#] 1520 내리막 길

📕 문제

📌 링크

📘 코드

namespace BOJ
{
    class No_1520
    {
        static int n, m;
        static int[] dx = new int[] { 1, 0, -1, 0 };
        static int[] dy = new int[] { 0, 1, 0, -1 };
        static int[,] arr = new int[500, 500];
        static int[,] cnt = new int[500, 500];

        static void Main()
        {
            using StreamReader input = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter output = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            int[] inputs = Array.ConvertAll(input.ReadLine().Split(), int.Parse);

            n = inputs[0];
            m = inputs[1];

            for(int i=0 ;i<n ;i++)
            {
                inputs = Array.ConvertAll(input.ReadLine().Split(), int.Parse);

                for(int j=0 ;j<m ;j++)
                {
                    arr[i, j] = inputs[j];
                    cnt[i, j] = -1;
                }
            }

            cnt[0, 0] = 1;

            output.WriteLine(DFS(n - 1, m - 1));
        }

        static int DFS(int x, int y)
        {
            if(cnt[x, y] != -1) return cnt[x, y];

            cnt[x, y] = 0;
            for(int dir=0 ;dir<4 ;dir++)
            {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if(nx>=0 && nx < n && ny >= 0 && ny < m)
                {
                    if(arr[x, y] < arr[nx, ny])
                    {
                        cnt[x, y] += DFS(nx, ny);
                    }
                }
            }

            return cnt[x, y];
        }
    }
}

📙 오답노트

로직의 시작점을 (0,0)이 아니라 (n-1, m-1)로 시작한다는 점이 색다르게 느껴졌다.
더 많은 문제를 풀어보며 다양한 풀이법을 경험해보며

📒 알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색