이번 문제 풀이 사실 봐버렸다. 거의 풀었다고 생각했는데 내가 생각한 방법으로는 도저히 풀리지가 않아서 그냥 풀이를 봤다.
바로 문제를 보자
문제를 읽어보면 낮은 방향으로만 진행한다고 한다. -> 사이클이 존재하지 않는 그래프이다.
가장 빠른게 도착하는게 아닌 도착하는 경우의 수를 구한다. -> BFS가 아닌 DFS를 여러 번 써야한다.
문제를 통해 2가지를 확인할 수 있다. 그런데 DFS만을 쓰는 경우에는 너무 많은 케이스가 존재한다. 실제로 DFS만으로 제출한다면 시간초과가 뜬다. 따라서 DFS만이 아닌 DP를 함께 활용해 주어야한다.
그럼 DP를 어떻게 활용해야 할지 고민을 해본다. DFS만 써서 시간초과가 나는 것은 빙빙 돌아 목적지에 도착하는 경우까지 기다려야 하기 때문이다. 그렇다면 빙빙 돌아 목적지에 도착하기 전에 탈출하는 조건을 만든다면 시간초과가 발생하지 않고 문제를 해결할 수 있다.
따라서 빙빙 도는 것을 방지하기 위해서는 이미 목적지에 잘 도착하는 경로를 표시해야한다!!
1. 목적지에 도착하는 경로에 대해서만 표시를 해줄 것.
2. 목적지에 이미 도착한 경로를 만날 경우 더 이상 DFS를 하지 않을 것.
3. 분기 하는 경우이면서, 목적지에 도착한 경우 둘의 경우의 값을 합쳐줄 것.
아마도 이해하기 힘들것이다. 따라서 그래프로 아주 잘 설명해주는 고수님의 블로그의 링크를 첨부한다. https://wootool.tistory.com/83
그럼 결과적으로 DFS를 재귀로 구현하고, return할때 dp를 갱신하는 방식으로 코딩을 진행한다.
M,N = map(int, input().split()) # 세로 가로
graph = []
for _ in range(M):
graph.append(list(map(int, input().split())))
visited = [[-1 for i in range(N)] for i in range(M)]
visited[M-1][N-1] = 1
# DFS
dy = [-1, 1, 0, 0] #상하좌우
dx = [0, 0, -1, 1]
def DFS(start):
y,x = start
if visited[y][x] != -1: #온적 있으면
return visited[y][x] # 해당 경우의 수를 그대로 넘겨준다.
tmp = 0
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if (0<=ny<M) and (0<=nx<N):# 인덱스 적정범위
if graph[ny][nx] < graph[y][x]:
tmp += DFS([ny,nx])
visited[y][x] = tmp # 분기한 경우에, 각 갈래의 경우의 수를 더해준다.
return visited[y][x] # 갱신된 자신의 경우의 수를 넘겨준다.
DFS([0,0])
print(visited[0][0])
결론 : DFS와 DP를 섞은 문제는 처음 풀어보았다. 아이디어가 필요한 문제였다. 참신한 접근법이라 완벽히 풀지는 못했지만 좋은 문제 같아서 비슷한 문제를 더 풀어보고 싶다.
'알고리즘' 카테고리의 다른 글
[python3] 백준 14360 풀이 ( 구슬 탈출 2, BFS, 방문체크 없음 ) (0) | 2021.08.13 |
---|---|
[python3] 백준 16236 풀이 ( 아기상어, 그래프, BFS, sort, pq? ) (0) | 2021.08.12 |
[python3] 백준 2293 풀이 ( 동전 1, 다이나믹 프로그래밍 ) (0) | 2021.08.10 |
[python3] 백준 9465 풀이 ( 스티커, 다이나믹 프로그래밍, 이차원 배열 ) (0) | 2021.08.09 |
[c++] 백준 1629 풀이 ( 곱셈, 분할 정복을 이용한 거듭제곱, long long ) (0) | 2021.08.09 |