[ programmers ] 경주로 건설 67259번 ( python )

문제

프로그래머스 67259 경주로 건설 풀이 ( 파이썬 )

https://programmers.co.kr/learn/courses/30/lessons/67259

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

 

풀이

co_board라는 최대값들을 가진 같은 크기의 2차원 리스트를 만들고 cost를 더한 값이 다음으로 진행하는 칸의 값보다 작다면 진행하는 칸의 크기를 갱신해 준다.

if c_dire + 2 == i or c_dire - 2 == i:
	continue

이 부분은 for문을 돌려서 방향을 탐색하는 중의 반대 방향은 탐색하지 않아도 되기 때문에 넣었다.

from collections import deque

def solution(board):
    answer = int(1e9)

    MAX_VALUE = int(1e6)

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    size = len(board)
    co_board = [[MAX_VALUE] * size for _ in range(size)]

    q = deque()
    
    q.append((0,0,1,0))
    q.append((0,0,2,0))

    while q:
        cx, cy, c_dire, c_cost = q.popleft()
        
        if cx == size - 1 and cy == size -1:
            answer = min(answer, c_cost)
            continue

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            cost = 0
            if nx < 0 or ny < 0 or nx >= size or ny >= size or board[nx][ny] == 1:
                continue
            if c_dire + 2 == i or c_dire - 2 == i:
                continue
            if c_dire == i:
                cost = 100
            else:
                cost = 500 + 100
            if co_board[nx][ny] >= c_cost + cost:
                co_board[nx][ny] = c_cost + cost
                q.append((nx, ny, i, c_cost + cost))
            
    print(answer)
    # for i in co_board:
    #     print(i)
    return answer