경주로 건설 - 2020 카카오 인턴십 문제 (python)

프로그래머스, 2020 카카오 인턴십 코딩테스트 기출 - 경주로 건설 LV3

https://programmers.co.kr/learn/courses/30/lessons/67259
BFS 문제, +움직이는 방향/cost 고려

👀 깃헙 소스

견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.

건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.

건설 비용은 4 x 100 + 1 x 500 = 900원 입니다.

코드

confirm을 dictionary로 구현,
{ 좌표 : 그 지점에서의 (최소)비용 }

# 파이썬
from collections import deque


def visitable(N, x, y, board):
    return 0 <= x < N and 0 <= y < N and board[y][x] == 0

def solution(board):
    N = len(board)
    Y, X, DIRECTION, SUM = 0, 1, 2, 3
    UP, DOWN, RIGHT, LEFT = 0, 1, 2, 3
    DELTAS = [(-1, 0, UP), (1, 0, DOWN), (0, 1, RIGHT), (0, -1, LEFT)]
    que = deque([])
    confirm = {(0, 0): 0}

    if board[1][0] == 0:  # 아래
        que.append((1, 0, DOWN, 100))
        confirm[(1, 0)] = 100
    if board[0][1] == 0:  # 오른쪽
        que.append((0, 1, RIGHT, 100))
        confirm[(0, 1)] = 100

    cand = []

    while que:
        cur = que.popleft()
        if cur[X] == N-1 and cur[Y] == N-1:
            cand.append(cur[SUM])

        for dy, dx, d in DELTAS:
            if cur[DIRECTION] == d:
                next_p = (cur[Y] + dy, cur[X] + dx, d, cur[SUM] + 100)
            else:
                next_p = (cur[Y] + dy, cur[X] + dx, d, cur[SUM] + 600)
            check = (next_p[Y], next_p[X])

            if visitable(N, next_p[X], next_p[Y], board):
                if check in confirm and confirm[check] < next_p[SUM]:
                    continue
                que.append(next_p)
                confirm[check] = next_p[SUM]

    return min(cand)

시험 당시 실패 코드

디렉션이랑 합까지 통으로 confirm에 넣어 확인하여 무한루프가 돌아감

방향까지 넣을필요 없음, 그 좌표에서 합이 이미 들어가 있는 합보다 작으면 바꿔치기 및 큐에 삽입해야함

# 택시비 적게내기 --> 가격까지 확인셋에넣어서 무한루프를 돌았음

from collections import deque


def visitable(N, x, y, board):
    return 0 <= x < N and 0 <= y < N and board[y][x] == 0


def solution(board):

    N = len(board)
    X, Y, DIRECTION, SUM = 0, 1, 2, 3
    UP, DOWN, RIGHT, LEFT = 0, 1, 2, 3
    DELTAS = [(-1, 0, LEFT), (1, 0, RIGHT), (0, 1, DOWN), (0, -1, UP)]
    que = deque([])
    confirm = set()

    if board[1][0] == 0:  # 아래
        que.append((0, 1, DOWN, 100))
        confirm.add((0, 1, DOWN, 100))
    if board[0][1] == 0:  # 오른쪽
        que.append((1, 0, RIGHT, 100))
        confirm.add((1, 0, RIGHT, 100))
    cand = []
    while que:
        cur = que.popleft()
        if cur[X] == N-1 and cur[Y] == N-1:
            cand.append(cur[SUM])

        for dx, dy, d in DELTAS:
            if cur[DIRECTION] == d:
                next_p = (cur[X] + dx, cur[Y] + dy, d, cur[SUM] + 100)
            else:
                next_p = (cur[X] + dx, cur[Y] + dy, d, cur[SUM] + 500)

            if visitable(N, next_p[X], next_p[Y], board) and next_p not in confirm:
                que.append(next_p)
                confirm.add(next_p)

    return min(cand)