[프로그래머스 Lv.3] 경주로 건설(파이썬)

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

프로그래머스

문제접근

 

다익스트라를 활용한다는 게 바로 들어왔다.

'최소비용'이라는 말을 읽자마자

heap을 활용해서 비용이 가장 적은 것을 빠르게 서치해야겠다 생각.

 

문제 설계

 

1. heappop,heappush를 활용해서 bfs랑 유사한 구도로 짠다.

2. 이전 방향에 따라 코너를 생성해야하기 때문에

초기 heap에 넣을때 상하좌우 모든 케이스를 넣어본다.

3. visited를 n*n*4(4는 상하좌우 방향을 의미)로 구현한다.

4. 조건에 맞게 범위,빈칸여부를 확인하면서 길을 만들어준다

 

 

문제에서 어려웠던 점

 

처음에 visited를 3차원으로 만들 생각을 하지 않아

제출 태케 2개가 틀렸다.

구글링과 질문게시판을 읽어보니

방향에 따라 값이 달라질 수 있어서

3차원배열로 구현한다는 게 2차원보다 훨씬 정확하다는 걸 알았다.

(2차원으로도 각 지점의 cost를 계산할 수 있긴한데

3차원이 보다 방향을 잘 표현할 수 있어서 더 정확함)

 

코드

 

from heapq import heappop, heappush

di = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def solution(board):
    answer = 1e9
    n = len(board)
    visited = [[[1e9] * n for _ in range(n)] for _ in range(4)]
    visited[0][0][0] = 0
    visited[1][0][0] = 0
    visited[2][0][0] = 0
    visited[3][0][0] = 0
    q = []
    heappush(q, [0, 0, 0, 0])
    heappush(q, [0, 0, 0, 1])
    heappush(q, [0, 0, 0, 2])
    heappush(q, [0, 0, 0, 3])
    while q:
        cost, x, y, pastD = heappop(q)
        # print(x,y,cost)

        if x == n - 1 and y == n - 1:
            answer = min(answer, cost)
            continue

        for d in range(4):
            if (d + 2) % 4 == pastD:
                continue

            nx = x + di[d][0]
            ny = y + di[d][1]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if board[nx][ny] == 1:
                continue

            nextCost = cost + 100
            if (d + 1) % 4 == pastD or (d - 1) % 4 == pastD:
                nextCost += 500

            if nextCost > visited[d][nx][ny]:
                continue

            visited[d][nx][ny] = nextCost
            heappush(q, [nextCost, nx, ny, d])

    return answer