1520번 백준(Baekjoon)

<문제>

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

<정답 코드>

초기에 bfs로 풀어본 결과 큐가 너무 많이 쌓여 메모리초과가 떴고

dfs로 풀었을 땐 시간초과가 떴었다. 한번 간적이 있는 길이라면 표시를 해둠으로써 

다시 방문하는 것을 막을 수 있었다. 먼저 길을 방문하며 0을 표시해두고 끝에 도달할 수 있는 길을 만나면

방문횟수를 리턴한다. 또한, 끝에 도달했다면 1을 리턴한다.

#include <iostream>
#include <cstdio>
#include <cstring>
 
#define MAX 501
 
using namespace std;
 
int row, col;
int map[MAX][MAX];
int visit[MAX][MAX];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
int dfs(int now_x, int now_y)
{
    if (now_x == col - 1 && now_y == 0)
        return 1;
    if (visit[now_x][now_y] == -1) {
        visit[now_x][now_y] = 0;
        for (int i = 0; i < 4; i++) {
            int next_x = now_x + dx[i];
            int next_y = now_y + dy[i];
            if (next_x >= 0 && next_y >= 0 && next_x < col && next_y < row) {
                if (map[now_x][now_y] > map[next_x][next_y])
                    visit[now_x][now_y] += dfs(next_x, next_y);
        }
    }
    return visit[now_x][now_y];
}
 
int main()
{
    scanf("%d%d", &row, &col);
    for (int y = row - 1; y >= 0; y--)
        for (int x = 0; x < col; x++)
            scanf("%d", &map[x][y]);
    memset(visit, -1, sizeof(visit));
    printf("%d\n", dfs(0, row - 1));
    return 0;
}