백준 1520번 내리막길

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

1520번: 내리막 길

 

 

 

입력)

첫째 줄:지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어짐

다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어짐.

M,N은 각각 500 이하의 자연수, 각 지점의 높이는 10000이하의 자연수

 

출력) 

첫째 줄에 이동 가능한 경로의 수 H를 출력

모든 입력에 대해 H는 10억 이하의 음이 아닌 정수

 

 

일단 2차원 배열을 만들어야 한다고 생각했다.

경우의 수를 다 구하는 생각을 했는데 코드 구현도 못할 뿐더러 해봤자 시간복잡도가 어마어마할 것 같아 감이 오지 않았다. 

이 문제는 DP배열과 DFS를 같이 써야 풀 수 있다고 한다. 

 

DFS 탐색으로만 문제를 풀면 시간 초과가 된다. ( 탐색한 곳을 또 탐색하게 되어서)

탐색 한 곳을 탐색처리하면 탐색한 곳은 다시 방문하지 않아 문제 풀기 불가능하다.

따라서  DP를 통해 모든 칸에 초기값을 -1로 초기화하고 탐색 시 0으로 다시 초기화해주어 탐색해야 하낟.

DP 값이 1이상의 값이라면 이전에 도착지까지 방문한 값으로, DP값을 리턴 받아 그 경로를 탐색하지 않고 다른 곳을 탐색한다.

결국 탐색한 곳은 다시 탐색하지 않고 반환받기 때문에 시간복잡도가 줄고 출발지부터 목적지까지 이동한 칸을 확인할 수 있다.

 

DFS (깊이 우선 탐색)

DFS는 그래프나 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나이다.

다음과 같은 특징을 갖는다.

1. 깊이 우선: 한 노드에서 출발하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.
2. 재귀적 구조 또는 스택(stack)을 사용: 재귀 함수나 명시적인 스택을 사용하여 구현된다.
3. 방문한 노드를 표시: 각 노드를 방문할 때마다 해당 노드를 이미 방문했다는 표시를 해둔다.

 

DP (동적 프로그래밍)

DP는 컴퓨터 프로그래밍에서 사용되는 알고리즘 설계 기법 중 하나이다.

다음과 같은 특징을 가진다.

1. 큰 문제를 작은 부분 문제로 나누기: 큰 문제를 작은 부분 문제들로 나누어 해결한다.
2. 중복되는 부분 문제: 작은 부분 문제들의 해답을 계산하고 저장해둠으로써 중복 계산을 피한다.
3. 상향식(bottom-up) 또는 하향식(top-down): 하향식은 큰 문제를 작은 부분 문제로 나누어 재귀 호출을 통해 해결하는 방식이며, 상향식은 작은 부분 문제부터 시작하여 반복문을 통해 해결하는 방식이다.

 

 

 

import sys
sys.setrecursionlimit(10 ** 9)


# DFS 탐색함수. 현재 위치 (x,y)에서 출발하여 목적지에 도착할 때까지의 경로의 개수를 구한다.
def dfs(x, y):

    # 목적지에 도착했으면 1을 반환하여 목적지까지 이동한 칸 모든 칸에 1을 더한다.
    if x == m - 1 and y == n - 1:
        return 1

    # 탐색하지 않은 곳이라면 탐색
    if dp[x][y] == -1:
        dp[x][y] = 0 # 탐색 유무

        # 상/하/좌/우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 내에 있고 현재 높이보다 낮은 높이라면
            if 0 <= nx < m and 0 <= ny < n:
                if graph[x][y] > graph[nx][ny]:
                    dp[x][y] += dfs(nx, ny) # (x, y)칸까지 몇번 이동하는지

    # 탐색한 곳이거나 탐색할 수 없는 곳이라면 자기 자신을 반환
    # 마지막에는 (0, 0)을 리턴
    return dp[x][y]

#지도의 세로 길이m, 가로 길이n을 입력
m, n = map(int, sys.stdin.readline().split())
#지도 각 칸의 높이 정보 입력
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
#각 칸을 방문했는지 여부를 저장하는 배열 초기화, 초기값은 -1
dp = [[-1 for _ in range(n)] for _ in range(m)]
#상하좌우 이동 위한 리스트 정의
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
#DFS 탐색 시작. 출발점 (0,0)에서 시작하여 목적지까지의 경로의 개수 출력
print(dfs(0, 0))

 

 

이번주 백준 과제는 나의 현 실력으로는 해결할 수 없었다. 많은 구글링을 통해 깨달았다..

코드는 원래도 잘 짜지 못했지만 코드는 몰라도 알고리즘은 어느정도 뼈대를 잡을 수 있었는데 그조차 하지 못해서 부족함을 많이 느꼈다.

이번주는 코드에 각주를 다는 식으로 풀이를 했는데 이게 더 보기 편한 것 같다.