[코딩테스트] #17. 백준 1520번: 내리막길

-문제: https://www.acmicpc.net/problem/1520

1520번: 내리막 길

어떻게 푸는지 몰랐는데 찾아보니까 dfs(깊이 우선탐색)+dp를 이용해서 풀어야하는 문제. 

 

-원리(출처: https://chldkato.tistory.com/114)

• dfs + dp로 목적지까지 도착할 수 있는지 검사한다
• 루프를 방지하기 위해 방문 확인 배열 c를 -1로 초기화하고 이동할 때마다 0으로 다시 설정해준다

 

• 1. 과정을 진행하면서 c에 이미 저장된 값이 0이면 목적지까지 갈 수 없으므로 0을 반환한다
• 2. 1 이상의 값이면 이전에 그만큼 방문 경로가 있으므로 해당 값을 반환해서 더해준다
• 3. -1이면 방문하지 않은 경로이므로 dfs + dp 수행 

 

-정답풀이: 

m,n = map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))

c=[[-1]*(n) for i in range(m)]   

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

def dfs(x,y):
    if x==m-1 and y ==n-1:
        return 1
    if c[x][y]!=-1:
        return c[x][y]
    c[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 a[nx][ny]<a[x][y]:
                c[x][y]+=dfs(nx,ny)
    return c[x][y]

print(dfs(0,0))

 

-전체풀이: 

 

• 파이썬으로 실행하면 Recurssion Error 때문에 Pypy3로 실행해야한다
• 세로 리스트가 입력된다는 것을 알고 문제를 풀어야한다 

 

• 초기값 설정. m이 컬럼 개수, n이 행 개수. 컬럼위주로 진행해야한다(4,5번라인)
• 이해 안가는 부분: 7번(밑에처럼 하면 mxn 행렬이 만들어지는 것 아닌가?)

 

• dx=[동,서,북,남] ,  dy=[동,서,북,남] 을 표현 한 것 같음 

 

• 인덱스가 행렬 가장 오른쪽 아래면 멈추고 1 반환한다 

 

• 값이 -1이 아니면 이 전에 방문된 기록이 있으므로 그 기록을 반환한다

 

• 이제 c[x][y]==-1이면 방문하지 않은 경로이고, 루프를 막아야하므로 0으로 초기화하고 시작한다 
• nx의 값으로는 x-1,x,x+1이 가능하다. ny도 마찬가지 
• 해당 인덱스의 동서남북 값을 비교하는 과정 

 

• (x,y)의 상하좌우 값 중에 작은 값들이 있을 경우에만 dfs값 넣는다 

 

• 왼쪽 가장 위 값부터 시작해서 (0,0)으로 대입하는 건가?