[카카오 인턴] 경주로 건설 with python

글쓰는데 재주가 없어 이해가 안되시면 댓글로 남겨주시면 친절하게 알려드리도록 하겠습니다  ~_~

 

링크

 

www.welcomekakao.com/learn/courses/30/lessons/67259?language=python3

코딩테스트 연습 - 경주로 건설

 

문제

 

경주로를 건설하는 데 필요한 최소 비용을 계산해야 되는 문제이다.

 

먼저 문제를 풀기 위해서 생각 해야 되는것은 내가 어떤 위치에 도착하기 전에 어느 방향에서 왔는가? 라는것을 알아야 한다. 내가 직진으로 왔는지 코너를 돌아서 왔는지

 

그러려면 이전 위치와 다음 도착한 위치를 비교를 저장해서 서로 비교를 해야 되겠구나를 알수 있게 된다.

 

그리고

 

코너의 도로를 만들때는 코너만 만드는것이 아니라 코너와 직진 도로를 같이 만든다는 것을 알수 있다.

 

마지막으로 dfs를 통하여 종점까지 탐색을 하고, dp를 이용하여 도로의 최솟값을 계속 갱신하면 값을 유추할 수 있다.

 

import collections
import heapq
import functools
import itertools
import re
import sys
import math
from typing import *

INF = 2222222222
d = [(-1, 0), (0, 1), (1, 0), (0, -1)]

dp_size = 30
dp = [[INF] * dp_size for _ in range(25)]
visited = [[False] * dp_size for _ in range(25)]

# 0 위로 직진, 1 오른쪽으로 직진, 2 아래로 직진, 3 왼쪽으로 직진
direct = [0, 1, 2, 3]


def solution(board) -> int:
    dp[0][0] = 0
    for dir, dd in enumerate(d):
        print(dir, dd[0], dd[1])
    dfs(0, 0, 1, board)
    dfs(0, 0, 2, board)

    return dp[len(board) - 1][len(board) - 1]


def dfs(h_x, h_y, h_dir, board) -> None:
    for dir, dd in enumerate(d):
        n_x, n_y = h_x + dd[0], h_y + dd[1]
        n_dir = direct[dir]
        n_cost = cost_calc(h_dir, n_dir)
        if n_x < 0 or n_x >= len(board) or n_y < 0 or n_y >= len(board) or board[n_x][n_y] == 1:
            continue

        if dp[n_x][n_y] < dp[h_x][h_y] + n_cost:
            continue

        dp[n_x][n_y] = dp[h_x][h_y] + n_cost
        dfs(n_x, n_y, n_dir, board)


def cost_calc(h_dir, n_dir) -> int:
    # 직선일때 cost
    if h_dir == n_dir:
        return 100

    # 코너를 돌때 cost
    else:
        return 600


if __name__ == "__main__":
    n = int(input())
    board = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

    solution(board=board)
    print(dp[len(board) - 1][len(board) - 1])