[프로그래머스] 경주로 건설 (python)

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

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

---

📍 Problem

벽이 존재하는 NxN 크기의 부지에 벽을 피해 (0, 0) 칸 부터 (N-1, N-1) 칸까지 도달하는 경주로를 건설한다. 이때 건설 가능한 경주로 중, 최소 비용의 경주로를 찾는다. 경주로 비용 조건은 다음과 같다.

1. 인접한 두 빈 칸을 상하 또는 좌우로 연결한 직선 도로는 100원
2. 경주로 연결시 두 직선 도로가 서로 직각으로 만나는 코너 형태로 건설시 500원 추가

---

💡 Solution

현재 위치에서 이동 가능한 방향을 결정해 최종 칸 (N-1, N-1) 까지 도달할 때까지의 비용을 계산하는 BFS 문제이다. 

주의해야할 점은 같은 칸에 도달하더라도 어떤 방향으로 방문했냐에따라 cost가 달라질 수 있다는 점이다.

 

따라서 visited 저장시, 해당 위치에 도달하게된 마지막 방향 정보까지 함께 저장해야하며, 해당 상태에 다시 방문하게 될 때, 예상되는 cost보다 이미 저장된 cost가 적을 경우 방문하지 않아야한다.

 

1. visited의 key는 ((위치 정보), (마지막 방향 정보)) 형태로 tuple로 묶어 관리했으며, 해당 key에 다시 접근하게 되었을 때 더 작은 cost가 들면 업데이트한다. 

2. 초기 node는 시작 위치 (0, 0)에서 이동할 수 있는 위치 (0, 1) 와 (1, 0) 를 추가해 BFS 탐색을 수행한다. 

3. 이동할 방향 정보와 노드의 마지막 방향 정보가 다르면 코너 비용을 추가한다. 

4. 최종 위치 (N-1, N-1) 에 도달할 때 서로 다른 방향 정보로 도달할 수 있다. 중간에 min cost를 업데이트하거나 마지막에 최종 min cost를 계산해야한다.

import sys
from collections import deque


class Node:
    def __init__(self, index, direction):
        self.index = index  # 위치 정보
        self.direction = direction  # 해당 위치에 도달하게된 방향 정보


def solution(board):
    size = len(board)
    straight = 100
    corner = 500
    cost = sys.maxsize

    q = deque()
    visited = {}
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    # 시작 위치에서 이동 가능한 위치
    if board[1][0] == 0:
        q.append(Node((1,0), (1,0)))
        visited[((1,0), (1,0))] = straight

    if board[0][1] == 0:
        q.append(Node((0,1), (0,1)))
        visited[((0,1), (0,1))] = straight

    while len(q) > 0:
        node = q.popleft()
        x, y = node.index
        node_cost = visited[(node.index, node.direction)]

        if x == size -1 and y == size - 1:
            cost = min(cost, node_cost)
        
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            
            if not 0 <= nx < size or not 0 <= ny < size:
                continue

            if board[nx][ny] == 1:
                continue

            _cost = node_cost + straight + (0 if (dx, dy) == node.direction else corner)

            if ((nx, ny), (dx, dy)) in visited and visited[((nx, ny), (dx, dy))] <= _cost:
                continue

            q.append(Node((nx, ny), (dx, dy)))
            visited[(nx, ny), (dx, dy)] = _cost
                
    return cost


if __name__ == '__main__':
    board = [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]]
    sol = solution(board)
    print(sol)