1학기 2주차 알고리즘 과제 (1520번 : 내리막 길)

 

1520번: 내리막 길 (acmicpc.net)

1520번: 내리막 길

 

문제

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

 

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

  

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

 

 

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

 

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

 

 

 

📌풀이

 

 

 

 

 

그림으로 되어있어서 직접 해보는게 알고리즘을 생각하기 좋을 것같아서 위와같이 풀이를 시도해봤다.

 

 

✔ 문제를 살펴봤을 때, 우선 제 1조건인 제일 왼쪽 위칸이 나타내는 지점에 세준이가 서있고, 제일 오른쪽 아래칸이 나타내는 지점으로 가고 싶어한다는 것과 2조건인 가능한 힘을 적게 들이고 싶어해서 높이가 더낮은 즉, 숫자가 더 낮은 곳으로만 이동한다는 점, 그리고 마지막 조건인 상하좌우 이웃한 곳끼리만 이동이 가능하다는 점을 이용해서 문제를 풀어야한다.

 

✔ 입력을 살펴봤을 때, 우선 input  함수를 써 M과 N을 입력을 받도록 해야한다.

그리고 수 비교를 해야하니까 int를 통해 형변환을 해야할 것 같다.

 

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

이 부분을 봤을 때, 어쨋든 저장하고 수를 비교해야하므로,  배열을 활용해야할 것 같은데, 다차원으로 쓰이고 있으므로 다차원배열을 사용해보도록한다.

 

✔ for 문을 통해 반복해서 수가 받아서 저장되도록 할 것이고, if문을 통해서 숫자가 상하좌우 중 더 낮을 경우에만 이동하여 -> 즉 현재위치를 저장하는 변수를 만들어 값을 계속 갱신해주도록 해야할 것 같다.

 

✔ 그리고 현재위치가 마지막 인덱스인 a45일경우 종료하도록 해서 몇가지 경로가 나올 수 있을 지 코드를 짜봐야할 것같다. 

 

 

생각은 되나, 코드를 짜는 것이 쉽지않다고 생각하면서 머리를 부여잡았는데, 어쩐지 골드였다 히히

심지어 컴파일 에러... 

이건 그냥 코드를 C랑 혼동한 부분이 생긴거였음

 

두번째 시도도 틀렸습니다.

근데 나는 온전히 내힘으로 이문제를 풀만한 실력이 안되는 것을 안다. 그럼 이제는 학습의 자세로, 다른사람들이 짠 코드를 공부해보는 게 나을 것 같다는 생각이 들었다.

 

 

Python - [백준]1520-내리막길 (velog.io)

Python - [백준]1520-내리막길

 

해당 문제는 DFS + DP를 이용한 문제였다.

 

DFS를 기본 개념으로 사용하지만 그것만 사용하게 된다면 무수히 많은 경우의 수를 낳기 때문에 불가능하고,

그래서 DP를 이용하여 연산횟수를 줄여주어야 한다고한다.

DP를 사용하기 위한 조건인 전체 문제의 최적해가 부분 문제의 최적해로 나누어지는지를 살펴 보아야 하는데,

이 문제를 시작점에서부터 도착점으로 가는 경로의 수를 구하는 문제에서, 임의의 점(x, y)에서 도착점 까지의 경우로 세분화 하여 구한다면, 그 어떤 경로로 (x, y)에 도착 하기만 해도 그 때부터의 경우의 수는 다시 구할 필요가 없다고 한다.

 

정리하자면, 도착 지점까지 가는 경우의 수는 도착 지점이 아닌 임의의 점들에서 도착지점까지 가는 경우의 수를 합한 것과 같다.

그렇다면, 어떻게 메모이제이션을 할 것이냐?

• DP 테이블을 -1로 초기화 하여 생성한다. 0이 아닌 -1인 이유는 방문여부(visted)를 알기 위하여 -1로 초기화 하기
• 시작 지점에서 출발하여 만약 DP테이블이 갱신 되지 않은 -1인 임의의 점을 만난다면 해당 지점부터 도착지점 까지 갈 수 있는 경로의 수를 재귀적으로 업데이트 해주기
• 만약 해당 지점의 DP테이블이 -1이 아닌 업데이트 되어있는 상태라면 더 진행 할 필요 없이, 그 지점이 부분 최적해가 되므로 그 지점의 DP테이블의 값을 바로 반환해주기.
• 종료 지점에 도착 한 경우, 1을 바로 반환해주기

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion) (tistory.com)

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

 

📌 메모이제이션이란?

 

기억되어야 할 것이라는 뜻의 라틴어에서 파생된 단어로, 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행속도를 빠르게 해주는 기법으로 동적 계획법(DP : 다이나믹 프로그래밍)의 핵심이 되는 기술이다.

 

[알고리즘] DP(동적계획법) | Floyd'.. : 네이버블로그 (naver.com)

[알고리즘] DP(동적계획법) | Floyd's Algorithm

 

 

📌 동적 계획법이란?

 

 

주어진 문제를 해결하기 위해서, 큰 문제를 여러 개의 하위 문제로 나눈 다음 그 결과를 저장해두었다가 필요할 때 결합하여 최종적인 해답을 도출해 내는 프로그래밍 기법이다.

 

📌 동적 계획법을 사용하는 경우는?

 

동적계획법은 하위 문제들에 대한 답을 저장해두었다가 재사용(메모제이션, Memoization)하므로 불필요한 계산이 중복되는 것을 방지하여 효율적으로 문제를 해결할 수 있다. 따라서 불필요한 중복 계산이더라도 매번 수행하는 재귀 알고리즘보다 더 적은 시간 안에 문제를 해결할 수 있다.

또한 동적계획법은 최적 부분 구조를 가진 문제에 적합하다. 최적 부분 구조란 큰 문제의 최적해를 작은 부분 문제의 최적해를 통해 구할 수 있는 것을 의미한다.

 

 

 

DFS 완벽 구현하기 [Python] (tistory.com)

DFS 완벽 구현하기 [Python]

 

 

 

📌 DFS란?

 

DFS란 Depth first search의 약자로서 그래프 자료에서 데이터를 탐색하는 알고리즘이다.

 

오른쪽에  A부터 J까지 노드가 연결되어 있는 그래프 자료를 볼 수 있습니다.

그래프에서 특정 노드를 찾으려고 할 때, 위에서 부터 찾느냐 혹은 옆에서부터 찾느냐 그 차이가 있다.

위에서 아래로 찾는 방식을 바로 DFS(Depth First Search)라고 부르는 것이다.

 

DFS의 기본 원칙

 

DFS에서 데이터를 찾을 때는 항상 "앞으로 찾아야 가야할 노드"와 "이미 방문한 노드"를 기준으로 데이터를 탐색을 합니다. ( 이 원칙이 핵심! )

그래서 특정 노드가 "앞으로 찾아야 가야할 노드"라면 계속 검색을 하는 것이고, "이미 방문한 노드"면 무시하거나 따로 저장하면 된다.

DFS를 구현할 때는 기본적으로 "스택/큐"를 활용할 수도 있고, "재귀함수를 통해 구현할 수도 있다.

 

 

코드

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def dfs(sx, sy):
    # 도착 지점에 도달하면 1(한 가지 경우의 수)를 리턴
    if sx == m-1 and sy == n-1:
        return 1

    # 이미 방문한 적이 있다면 그 위치에서 출발하는 경우의 수를 리턴
    if dp[sx][sy] != -1:
        return dp[sx][sy]
    
    ways = 0
    for i in range(4):
        nx, ny = sx + dx[i], sy + dy[i]
        if 0 <= nx < m and 0 <= ny < n and graph[sx][sy] > graph[nx][ny]:
            ways += dfs(nx, ny)
    
    dp[sx][sy] = ways
    return dp[sx][sy]


m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1] * n for _ in range(m)]
dx, dy = [1,-1,0,0], [0,0,1,-1]

print(dfs(0,0))

 

• sys.setrecursionlimit(10 ** 8): 재귀 제한을 늘려준다. 파이썬의 기본 재귀 제한은 작기 때문에, 문제에서 요구하는 크기의 재귀 호출을 위해서 재귀 제한을 늘려준다.
• input = sys.stdin.readline: 코드에서 사용할 input 함수를 sys.stdin.readline으로 재정의합니다. 이렇게 하면 입력 속도가 향상된다.
• dfs(sx, sy): DFS(깊이 우선 탐색) 함수를 정의하고, 현재 위치 (sx, sy) 에서 출발하여 목표 지점까지 가는 경로의 수를 계산한다.
• if sx == m-1 and sy == n-1:: 도착 지점에 도달하면 1(한 가지 경우의 수)를 반환한다.
• if dp[sx][sy] != -1:: 이미 방문한 적이 있다면 그 위치에서 출발하는 경우의 수를 반환합니다. 이는 메모이제이션(Memoization)을 위한 코드이다.
• for i in range(4):: 상하좌우로 이동하면서 내리막길인 경우만을 고려하여 경우의 수를 누적한다.
• dp[sx][sy] = ways: 메모이제이션을 통해 중복된 계산을 피하고, 각 위치에서의 경우의 수를 저장한다.
• m, n = map(int, input().split()): 지도의 세로 길이 m과 가로 길이 n을 입력받는다.
• graph = [list(map(int, input().split())) for _ in range(m)]: 지도의 정보를 입력받습니다. 이는 각 칸의 높이 정보를 저장하는 2차원 리스트이다.
• dp = [[-1] * n for _ in range(m)]: 각 위치에서의 경우의 수를 저장할 메모이제이션 테이블을 초기화한다.
• dx, dy = [1,-1,0,0], [0,0,1,-1]: 상하좌우로 이동하는 경우를 나타내는 리스트를 정의한다.
• print(dfs(0,0)): 출발 지점인 (0, 0)에서 시작하여 DFS 함수를 호출하고, 결과를 출력한다.

 

 

 

알고리즘수업을 통해 얼핏 들어본 적있는 것 같긴하지만, 아직 본격적으로 배우지 않아서, 자료구조시간에 배운다면 오늘 학습한 이내용이 많이 도움이 될 것 같고, 제대로 공부해서 구사하고 싶다.

 

 

[참고 학습 자료]

 

 

[백준(파이썬/Python)] 1520_내리막 길 - DFS, DP (tistory.com)

[백준(파이썬/Python)] 1520_내리막 길 - DFS, DP

[baekjoon] 백준 1520번(파이썬): 내리막 길 (tistory.com)

[baekjoon] 백준 1520번(파이썬): 내리막 길