백준 1520번: 내리막 길 (dp, dfs)

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

1520번: 내리막 길

 

입력

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

출력

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

 

---

문제를 너무 만만하게 봤다

처음엔 bfs로 풀려고 했는데..

생각처럼 안 됐다

여러갈래로 뻗어나가니 경로를 어떻게 셀 지도 막막하고..

중간에 주석덩어리가 bfs로 풀어보려던 흔적이다

 

왠지 dfs로 풀면...

간단하게 되지않을까 싶어 dfs로 시도했는데

방문처리를 어떻게 할까 떠올리는게 쉽지않아서 

다른사람 코드를 참고했다

 

import sys
from collections import deque
input=sys.stdin.readline

n,m=map(int,input().split()) #세로n,가로m
graph=[]
for i in range(n):
    graph.append(list(map(int,input().split())))


dx=[1,-1,0,0]
dy=[0,0,-1,1]
# def bfs(x,y):
#     q=deque()
#     visited=[[0]*m for i in range(n)]
#     q.append((x,y))
#     visited[x][y]=1
#     count=0
#     while q:
#         x,y=q.popleft()
#         if x==n-1 and y==m-1:
#             count+=1
#         for i in range(4):
#             nx=x+dx[i]
#             ny=y+dy[i]
#             if nx<0 or ny<0 or nx>=n or ny>=m:
#                 continue
#             if graph[nx][ny]<graph[x][y] and visited[nx][ny]==0:
#                 q.append((nx,ny))
#                 visited[nx][ny]=1
# count=0
dp=[[-1]*m for i in range(n)]
def dfs(x,y):
    
    if x==n-1 and y==m-1:
        return 1
    
    if dp[x][y]!=-1:
        return dp[x][y]

    ways=0
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or ny<0 or nx>=n or ny>=m:
            continue
        if graph[nx][ny]<graph[x][y]:
            ways+=dfs(nx,ny)
    dp[x][y]=ways
    print()
    # for i in dp:
    #     for j in i:
    #         print(j,end=' ')
    #     print()
    return dp[x][y]    

print(dfs(0,0))

dp와 dfs를 같이 사용한 코드

https://velog.io/@nathan29849/BAEKJOON-1520-%EB%82%B4%EB%A6%AC%EB%A7%89-%EA%B8%B8-DFS-BFS-python이 블로그 글이 도움이 됐다..

 

dp에 경로의 수를 기록하는데, 목적지부터 출발위치까지 역으로 채워진다

길이 나눠지는 교차로의 값은 나눠진길1에서 갈수있는 경로의 수 + 나눠진길2에서 갈 수 있는 경로의 수

이런식으로 더해지고..

쭉쭉 가서 마지막에 0,0좌표의 dp값이 결정나는데 이 값을 출력해주면 된다

 

나는 dp가 어떤 순으로 채워지는지 눈으로 보고싶어서

dp가 갱신될 때마다 dp를 출력하는 몇 줄의 코드를 추가해서 직접 보면서 이해했다 (코드 마지막쯤에 있는 주석덩어리)

 

......

..........