2020 카카오 인턴십 경주로 건설 풀이 With Python

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/67259

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

시험 당시에 이 문제는  BFS(너비 우선 탐색)으로 해결해야겠다는 생각이 들었고, 30분 정도 끙끙대며 코드를 수정하며 맞혔습니다. 문제의 핵심은 각 지점마다 들어갈 때의 방향을 체크하여 같은 방향으로 들어갔을 때 만약 비용이 이전에 방문하였을 때보다 적거나 혹은 방문하지 않았을 경우에만 방문하도록 하는 것이고 이를 해결하기 위해 dict 자료구조를 이용하였습니다. 그리고 기존 방향과 수직이 되도록 진행하였다면 비용을 500원을 추가하는 것이 아닌 600원을 추가하여야 한다는 것입니다.  왜 그런지는 문제를 보시고 곰곰이 생각해보시길 권장하겠습니다. 모르시겠으면 댓글 남겨주시면 답변드리겠습니다. 소스코드는 아래와 같습니다. 

def solution(board):
    n = len(board)
    from collections import deque
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    answer = float('inf')
    queue = deque()
    # x좌표 y좌표 방향 비용 순서로 큐에 넣습니다.(방향은 맨처음 시작할 때 -1로 설정)
    queue.append((0, 0, -1, 0))
    visit = {(0, 0, 0): 0, (0, 0, 1): 0, (0, 0, 2): 0, (0, 0, 3): 0}
    while queue:
        x, y, dir1, cost = queue.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if -1 < nx < n and -1 < ny < n and not board[nx][ny]:
                newcost = cost
                # 방향이 -1인 경우는 가장 처음에는 방향이 없으므로 비용에 100을 추가
                if dir1 == -1:
                    newcost += 100
                # 기존 방향과 진행 방향이 평행한 경우
                elif (dir1 - d) % 2 == 0:
                    newcost += 100
                # 기존 방향과 진행 방향이 수직인 경우
                else:
                    newcost += 600
                # 목적지에 도착하였을 경우 정답 값과 비교하여 더 작은 것으로 정답 값을 경신
                if nx == n - 1 and ny == n - 1:
                    answer = min(answer, newcost)
                # 기존에 방문하지 않았거나 방문하였을 때보다 비용이 적을 경우에만 큐에 넣습니다.
                elif visit.get((nx, ny, d)) is None or visit.get((nx, ny, d)) > newcost:
                    visit[(nx, ny, d)] = newcost
                    queue.append((nx, ny, d, newcost))
    return answer

소스코드에 대한 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다. 읽어주셔서 감사합니다. :-)