[プログラマー]コース建設複記
13345 ワード
質問する
https://programmers.co.kr/learn/courses/30/lessons/67259
さまよう過程
まず最初はdfsで解決した.何が問題なのか分かりませんが、24番のテストケースは返されませんでした.
一般的なdpとは異なり,以前の決定は次のステップにも影響を及ぼす.
100と120の2つの値が(1,1)ノードに入ると仮定すると、通常のdpであれば、最小値100が格納される.ただし、最小値100を記憶して方向を変えると、次の隣接座標は150となる.しかし、120を保存した後に方向を変えなければ、130の最小値が発生する可能性があるが、これを考慮することはできない.
では、すべての方向を考えるべきです.この過程で長い間うろうろしていた.
考慮すべき
code
# 자동차 경주로 건설 N*N
# 0은 빈칸, 1은 채워져있다
# 직선도로 100원, 코너 500원
# dfs
def solution(board):
answer = 0
dxy = [[0,1],[0,-1],[1,0],[-1,0]]
visited = [[False]*len(board[0]) for _ in range(len(board))]
res = float("inf")
memo = [[float("inf")]*len(board[0]) for _ in range(len(board))]
def dfs(x,y,direct,pay):
nonlocal res
if pay> res:
return
if pay <= memo[x][y]: ##### 다시보기
memo[x][y] = pay
else:
return
if x == len(board)-1 and y == len(board[0])-1:
return
for k in range(4):
nx, ny = x+dxy[k][0], y +dxy[k][1]
if 0<= nx < len(board) and 0<=ny<len(board[0]):
if not visited[nx][ny] and board[nx][ny] == 0:
visited[nx][ny] = True
if k != direct:
dfs(nx,ny,k, pay+600)
else:
dfs(nx,ny,k, pay+100)
visited[nx][ny] = False
return
for i in range(4):
nx, ny = dxy[i][0], dxy[i][1]
if 0<= nx < len(board) and 0<=ny<len(board[0]):
if board[nx][ny] == 0:
visited[nx][ny] = True
print(memo)
dfs(nx,ny,i,100)
return memo[len(board)-1][len(board)-1]Reference
この問題について([プログラマー]コース建設複記), 我々は、より多くの情報をここで見つけました https://velog.io/@kkmn972/프로그래머스-경주로-건설-복기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol