문제 링크 - https://www.acmicpc.net/problem/1520
그래프탐색과 방문리스트를 담아서 쓰면 간단하게 풀릴거라 생각했다.
최초코드 (틀림)
노드를 탐색하며 지나온 좌표를 리스트에 담아서 종점에 도착하거나 , 이미 지나간 경로의 노드를 방문하면 갖고 있던 배열의 좌표에 가중치를 적용한다.
https://www.acmicpc.net/problem/1520
import sys
from collections import deque
input= sys.stdin.readline
from copy import deepcopy
dy,dx= [0,0,1,-1],[1,-1,0,0]
n,m = map(int,input().split())
# 중첩되는 경로 도착시, 이미 진행한 경로를 또 지나가면서 탐색함 - > 시간초과
# 각 좌표에 도착하는 노드를 모두 체크 후 각 노드에 모두 추가하기
matrix = [list(map(int,input().split())) for __ in range(n)]
dp = [[0]*(m) for __ in range(n)]
def check_point(path_matrix):
for py,px in path_matrix: # 경로 도달시 패스노드 체크
dp[py][px]+=1
def dfs(sy,sx):
result = 0
stack = []
stack.append(((sy,sx,[])))
while stack:
y,x,path_matrix = stack.pop()
for i in range(4):
ny,nx = y+dy[i],x+dx[i]
if 0<=ny<n and 0<=nx<m and matrix[ny][nx]<matrix[y][x]:
if (ny,nx) == (n-1,m-1):
check_point(path_matrix)
result+=1
continue
elif dp[ny][nx]>0:
check_point(path_matrix)
result+=dp[ny][nx]
continue
next_path = deepcopy(path_matrix)
next_path.append((ny,nx))
stack.append((ny,nx,next_path))
return result
print(dfs(0,0))
경우의 수가 작은범위에서는 맞았지만 분기가 많은 테스트케이스의 경우에서 값이 달랐다.
ex)
2 18
98 91 89 80 76 74 65 58 50 49 44 32 26 23 17 15 14 8
95 91 83 82 70 67 65 55 54 50 41 27 22 20 14 10 7 3
왜인지 생각을 해보니 check_point의 함수에서 값을 1씩 추가해서 문제가 되었다. 현재 도착해서 체크포인트함수에 들어가는 현재노드를 도착할 수 있는 경우의 수를 더해줘야하는데 단순하게 한번 방문하니 1 추가해야지 해서 답이 다르게 나왔다 이후에 변경한 check_point함수
def check_point(path_matrix,padd):
for py,px in path_matrix: # 경로 도달시 패스노드 체크
dp[py][px]+=padd # 지나온 경로에 현재 도달 할 수 있는 분기 더해주기
코드 변경 후 테스트케이스의 답은 모두 맞았지만 백준 ac에서 40%쯤 시간 초과가 나왔다,
이유는 check_point함수를 for문으로 순회하며 각 노드에 방문값을 계속해서 추가해주는데, 각 좌표에서 범위가 넓어지고 분기가 달라질 수록 경우의수가 커지면 기하급수적으로 방문범위가 넓어지고 중복해서 방문해서 연산횟수가 늘어난다.
-> 방문리스트를 갖고 탐색하지말고 방문시 실시간으로 방문횟수 갱신하기
# # 중첩되는 경로 도착시, 이미 진행한 경로를 또 지나가면서 탐색함,
# # 경로중 분기점일떄 , 분리되어 도착하는 경로 수만 세어서 도착시
# # 현재 도달가능 경로수 * 도착지점 도달 가능 경로수
import sys
import heapq
input= sys.stdin.readline
from copy import deepcopy
dy,dx= [0,0,1,-1],[1,-1,0,0]
n,m = map(int,input().split())
matrix = [list(map(int,input().split())) for __ in range(n)]
visited = [[0] * m for __ in range(n)]
def bfs(sy,sx):
q =[]
heapq.heappush(q,(-matrix[sy][sx],sy,sx))
visited[sy][sx]=1
while q:
now,y,x =heapq.heappop(q)
for i in range(4):
ny,nx = y+dy[i],x+dx[i]
if 0<=ny<n and 0<=nx<m and matrix[ny][nx]<matrix[y][x]:
if visited[ny][nx]==0:
heapq.heappush(q,(-matrix[ny][nx], ny, nx))
visited[ny][nx] += visited[y][x]
bfs(0,0)
print(visited)
print(visited[n-1][m-1])
1.시작점에서부터 큰 값을 가지고 작은 값을 탐색해야 하기에 출발 시 제일 큰 값을 가지게 된다.
2. 이를 활용해서 최대힙을 사용하여 제일 큰 값부터 낮은 값으로 내려가며 탐색하기,
3. 현재 진행 가능한 좌표들중 가장 큰 값을 먼저 진행하여 내림차순으로 탐색을 진행하게 된다,
4. 이미 지나간 경로를 방문하게 된다면 현재 노드의 분기횟수 + 지나간 노드의 분기횟수를 더해주며 visited값 갱신
5. n-1,m-1 마지막지점에 지나갈 수 있는 경로의 수 리턴