[백준] 1520. 내리막길 Python

문제 링크 : 1520 내리막길

1520번: 내리막 길

 

풀이 코드 : GIthub
 

문제

 

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

 

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

 

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

 

문제

풀이 

처음에는 간단한 DFS문제로 생각하였다. 다음과 같은 방법으로 풀이를 생각하였다.

• DFS로 0,0 부터 주변의 높이가 낮은 지점을 방문한다.
• 방문한 지점은 방문하였다고 표기한다.
• DFS로 목표지점에 방문하면 count를 1 더한다
• 모든 DFS를 수행하면 count를 출력한다.

 

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split(' '))

maps = []

for i in range(n):    
	maps.append(list(map(int, input().split())))


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


dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

count = 0


def dfs(x, y):
    global count
    if x == n-1 and y == m-1:
        visited[x][y] = 0
        count += 1
        return
    for direction in range(4):
        new_dx = x + dx[direction]
        new_dy = y + dy[direction]
        if 0 <= new_dx < n and 0 <= new_dy < m:
            if maps[new_dx][new_dy] == 0 or visited[new_dx][new_dy] == 1:
                continue
            else:
                if (maps[new_dx][new_dy]) < (maps[x][y]) and visited[new_dx][new_dy] == 0:
                    visited[new_dx][new_dy] = 1
                    dfs(new_dx, new_dy)
        visited[x][y]  = 0




dfs(0, 0)

print(count)

 

 

결과

 

시간초과가 나왔다.

 

문제점은 다음과 같았다.

 

문제에서 목적지 까지 가는 방법은 아래와 같이 3가지가 있다. 

여기서 2번째 3번째 [20 -> 17 -> 15 -> 10]부분이 겹친다.

그렇다면 3번째 경로에서 20 부분에 들어갔을 때 더이상 진행할 필요가 없고(어차피 목적지에 도달할 수 있으므로) 바로 count에 추가하면 된다.

 

두번째 풀이

https://fre2-dom.tistory.com/251

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

위 블로그 글을 참고하여 풀었다.

DP를 활용하여 중복된 연산을 피하는 것이 핵심이였다.

 

코드

import sys
from collections import deque
sys.setrecursionlimit(10 ** 9)

n, m = map(int, sys.stdin.readline().split(' '))

maps = []

for i in range(n):    
	maps.append(list(map(int, input().split())))


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



dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def dfs(x, y):
    if x == n-1 and y == m-1:
        return 1
    
    if visited[x][y] == -1:
        visited[x][y] = 0

        for direction in range(4):
            new_dx = x + dx[direction]
            new_dy = y + dy[direction]

            if 0 <= new_dx < n and 0 <= new_dy < m:    
                if maps[new_dx][new_dy] < maps[x][y]:
                    visited[x][y] += dfs(new_dx, new_dy)

    return visited[x][y]

                    




print(dfs(0, 0))

 

바뀐것은 visited를 DP로 활용하며 목적지에 방문한 루트를 또 방문하면 목적지에 방문한 것으로 가정하고 DFS를 끝내는 것이다.

이로써 중복된 방문을 피해 시간초과를 피할 수 있었다.