[프로그래머스] 경주로 건설 복기
문제
https://programmers.co.kr/learn/courses/30/lessons/67259
헤매는 과정
일단 처음에는 dfs로 풀었다. 무엇인 문제 인지 모르겠지만, 테스트 케이스 24번이 돌아가지 않았다.
일반적 dp랑 다른점은 이전에 한 의사결정이 다음에도 영향을 미친다는 것이다.
만약 100과 120 두 개의 값이 (1,1) 노드에 들어왔다고 가정하자 일반적인 dp라면 최소값 100을 저장할 것이다. 하지만 최소값 100을 저장 후에 방향이 바뀌면 다음 인접 좌표는 150이 된다. 하지만 이전에 120을 저장 후 방향이 바뀌지 않으면 130의 최소값이 발생할 수 있지만, 이를 고려할 수 없다.
그렇다면 모든 방향에 대해서 고려해주어야 하는 것이 맞다. 이 과정에서 많이 헤맸다.
생각해 주어야 할 것
- 처음 시작을 생각해 주어야 한다. (0,0) 지점에서 갈 수 있는 좌표는 (1,0) 과 (0,1)이고, 이 두개 모두 경우에 비용은 100이다. 방향을 하나만 넣어 준다면 두 좌표중 하나의 좌표에는 500이 더해진 값이 저장 될 것이다. 때문에 과대 비용이 저장되고 다른 방향에 대해서는 고려할 수 없다. 그렇다면 두 방향에 대해서 queue에 한번에 저장하면 어떻게 될까? 정답은 아니다 하지만 확실히 왜인지를 모르겠다.
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]
Author And Source
이 문제에 관하여([프로그래머스] 경주로 건설 복기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kkmn972/프로그래머스-경주로-건설-복기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)