[프로그래머스] 경주로 건설 복기

문제

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]