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

문제

• NxN 경주로 부지의 (0, 0)에서 출발해 (N-1, N-1) 까지 경주로를 건설하는 최소 비용 구하기
  • 3 <= N <= 25
• 경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결해 건설하고, 벽이 있는 칸에는 건설할 수 없다.
• 직선도로는 100원, 코너는 500원이 추가로 든다.

 

풀이 1

• 최단 경로 구하기 문제
  • 같은 방향으로 이동하면 100원, 방향을 바꿔 이동하면 600원

 

answer = 1e9
dx = (-1, 1, 0, 0)  # 상, 하, 좌, 우
dy = (0, 0, -1, 1)

def dfs(board, x, y, n, price, d) :
    global answer

    if x == n-1 and y == n-1 :
        answer = min(price, answer)
        return
    if price >= answer :
        return
    
    board[x][y] = -1
    for i in range(4) :
        nx, ny = x+dx[i], y+dy[i]
        
        if 0 <= nx <= n-1 and 0 <= ny <= n-1 and board[nx][ny] == 0 :
            cost = 100 if i == d else 600
            dfs([b[:] for b in board], nx, ny, n, price+cost, i)
    
    
def solution(board):
    n = len(board)

    board[0][0] = -1
    if board[1][0] == 0 :
        dfs([b[:] for b in board], 1, 0, n, 100, 1)
    if board[0][1] == 0 :
        dfs([b[:] for b in board], 0, 1, n, 100, 3)
    
    return answer

 

테스트 1 〉	통과 (0.06ms, 10.4MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.10ms, 10.2MB)
테스트 5 〉	통과 (0.06ms, 10.4MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (54.34ms, 10.3MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	통과 (1.66ms, 10.3MB)
테스트 14 〉	통과 (17.71ms, 10.3MB)
테스트 15 〉	통과 (671.61ms, 10.3MB)
테스트 16 〉	실패 (시간 초과)
테스트 17 〉	실패 (시간 초과)
테스트 18 〉	실패 (시간 초과)
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	통과 (61.93ms, 12.3MB)
테스트 21 〉	통과 (77.13ms, 13MB)
테스트 22 〉	통과 (0.12ms, 10.3MB)
테스트 23 〉	통과 (0.13ms, 10.3MB)
테스트 24 〉	통과 (0.11ms, 10.4MB)
테스트 25 〉	통과 (0.12ms, 10.3MB)

 

풀이 2

• 경우의 수를 더 줄여야한다.
• 방문하지 않은 칸이거나 더 적은 비용으로 이동 가능한 경우만 방문하도록 한다.

case14 실패

answer = 1e9
dx = (-1, 1, 0, 0)      # 상, 하, 좌, 우
dy = (0, 0, -1, 1)

def dfs(board, x, y, n, price, d) :
    global answer

    if x == n-1 and y == n-1 :          # 마지막 칸 도달
        answer = min(price, answer)
        return
    
    if price >= answer:                 # 최솟값이 될 수 없는 경우             
        return
    
    for i in range(4) :
        nx, ny = x+dx[i], y+dy[i] 
        
        # 다음 칸으로 이동 가능한 경우
        if 0 <= nx <= n-1 and 0 <= ny <= n-1 :
            cost = 100 if i == d else 600   # 방향이 같으면 100원, 다르면 600원
            
            # 방문하지 않은 칸이거나, 더 적은 비용으로 이동이 가능한 경우만 방문
            if board[nx][ny] == 0 or board[nx][ny] >= price+cost :
                board[nx][ny] = price+cost  # 다음 칸 이동 표시
                dfs(board, nx, ny, n, price+cost, i)
    
    
def solution(board):
    n = len(board)
    
    board[0][0] = -1    # 시작 칸 표시
    # 아래로 이동
    if board[1][0] == 0 :
        board[1][0] = 100
        dfs([b[:] for b in board], 1, 0, n, 100, 1)
        board[1][0] = 0
    # 오른쪽으로 이동
    if board[0][1] == 0 :
        board[0][1] = 100
        dfs([b[:] for b in board], 0, 1, n, 100, 3)
    
    return answer

 

 

풀이 3

• 방향만 바꿔줬더니 통과
  • 변경 전
    dx = (-1, 1, 0, 0)      # 상, 하, 좌, 우
    dy = (0, 0, -1, 1)
  • 변경 후
    dx = (0, 1, 0, -1)      # 우, 하, 좌, 상
    dy = (1, 0, -1, 0)

 

References

• 프로그래머스 Lv3 경주로 건설