[알고리즘 / 백준] 1520 - 내리막 길

www.acmicpc.net/problem/1520

1520번: 내리막 길

 

문제는 위와 같으며, 지점의 높이를 이차원 배열로 저장하고 해당 배열과 동일하게 특정 위치를 방문했는지 알 수 있는 배열을 생성한 뒤 -1로 초기화 합니다.

 

방문했던 위치가

- 도착 지점과 같은 경우 1을 반환하고

- 한번이라도 방문한 적이 있는 경우(저장된 값이 -1이 아닌 경우)는 해당 위치에 지금까지 방문했던 값을 반환하고

- 두 가지 경우가 아닌 경우는 상하좌우로 이동할 수 있는지 확인하고 이동하려는 위치의 높이가 더 낮은 경우 현재 위치에 방문 값을 더한 뒤 그 값을 반환합니다.

 

과정을 표로 살펴보면 다음과 같습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin


def dfs(x, y):
    if x == m - 1 and y == n - 1:  # 도착점에 도달한 경우
        return 1
    if visited[x][y] != -1:  # 한번 이상 방문한 적이 있는 경우
        return visited[x][y]
    visited[x][y] = 0  # 한번도 방문한 적 없는 경우 +1 해서 0으로 만들고
    for i in range(4):  # 상하좌우 위치를 순서대로 확인하며
        next_x = x + dx[i]
        next_y = y + dy[i]
        if 0 <= next_x < m and 0 <= next_y < n:  # 지도 안에 다음 위치가 존재하고
            if height[next_x][next_y] < height[x][y]:  # 현재 위치보다 이동하려는 다음 위치가 낮은 경우 (내리막길인 경우)
                visited[x][y] += dfs(next_x, next_y)  # 그 다음 위치까지 이동한 (방문한 적 있는) 경우의 수를 현재 위치에 더하기
    return visited[x][y]


m, n = map(int, stdin.readline().split())
height = []
for _ in range(m):
    height.append(list(map(int, stdin.readline().split())))

visited = [[-1] * n for _ in range(m)]

# 상하좌우 이동할 위치를 x, y 좌표 나눠서 표시
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

print(dfs(0, 0))

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static int m;
    private static int n;

    private static int[][] height;
    private static int[][] visited;

    private static int[] dx = {1, -1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        height = new int[m][n];
        for (int i = 0; i < m; i++) {
            height[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        visited = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(visited[i], -1);
        }

        System.out.println(dfs(0, 0));
    }

    private static int dfs(int x, int y) {
        if (x == m - 1 && y == n - 1) {
            return 1;
        }

        if (visited[x][y] != -1) {
            return visited[x][y];
        }

        visited[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
                if (height[x][y] > height[nextX][nextY]) {
                    visited[x][y] += dfs(nextX, nextY);
                }
            }
        }
        return visited[x][y];
    }
}