[2020 카카오 인턴십] 경주로 건설

• 문제 푸는 시간 : 42분
• 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/67259

• 문제 정보

  • 0은 비어 있음 / 1은 채워있음
  • 출발 지점 : (0,0) / 도착 지점 (N-1,N-1)
  • 벽이 있는 곳은 건설 할 수 없다.
  • 경주로의 출발점은 (0, 0) 칸, 도착점은 (N-1, N-1) 칸
  • 도착점은 (N-1, N-1) 칸을 연결하여 건설할 수 있다.

• 입력

  • 도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board

• 출력

  • 경주로를 건설하는데 필요한 최소 비용을 return

• 코드

from collections import deque
def solution(matrix):

    N, M = len(matrix), len(matrix)
    dx = [0, -1, 0, 1]  # 상 좌 하 우
    dy = [-1, 0, 1, 0]

    def iswall(nx, ny):
        if nx < 0 or ny < 0:
            return False
        if nx >= N or ny >= M:
            return False
        if matrix[nx][ny] == 1:
            return False
        return True

    def bfs(start):
        queue = deque([start])
        matrix[0][0]= 1
        min_money = [[100000000] * N for _ in range(M)]
        min_money[0][0] = 0

        while queue:
            x,y,cost,head = queue.popleft() # 좌표
            for i in range(4): # 상 하 좌 우 좌표 살피기
                nx, ny=x+dx[i], y+dy[i]
                if iswall(nx,ny) :
                    if head != i: # 곡선 도로(모서리 + 직선)
                        n_cost = cost+ 600
                    else : # 직선 도로(직선)
                        n_cost = cost + 100
                    if n_cost < min_money[nx][ny]: # 최솟값인 경우
                        min_money[nx][ny] = n_cost
                        queue.append([nx, ny, n_cost, i])
        return min_money[-1][-1]
    return min(bfs((0,0,0,2)),bfs((0,0,0,3))) # 시작은 우, 하

matrix = [[0,0,0],[0,0,0],[0,0,0]]
print(solution(matrix))