Python) 프로그래머스. 경주로 건설
문제 링크
문제
- 건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.
- 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.
- 설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.
- 경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.
- 경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.
- 이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
- 또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
- 건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다.
-
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.
- 도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.
제한
- board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
- board 배열의 각 원소의 값은 0 또는 1 입니다.
- 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
- 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
- board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
- 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.
👀 풀이
BSF로 풀 수 있을거 같은데 방향을 어떻게 해야 하는 건가 고민하다가 질문 게시판을 참고했다.
- 비용을 저장할 테이블,
dp배열을 3차원 배열로 만들면서 무한대(1e9)로 초기화한다.dp[방향][y][x] - 시작 지점은 비용이 0이니까 각 방향 인덱스별 시작지점만 0으로 초기화 한다.
BFS에서 사용할 큐를 만든다.(덱 사용)- 큐에 들어갈 값은
(y, x, 비용, 방향)
- 큐에 들어갈 값은
- 시작 지점에서 오른쪽과 아래로 가는 비용은 100원, 방향은 각각 오른쪽과 아래로 정해져 있다. 두 위치에 벽이 없으면 각각의 비용과 방향을 큐에 추가한다.
BFS로 상하좌우 방향을 탐색하면서 최저 비용으로 갱신한다.- 5번 과정이 끝나면 4방향 인덱스를 순회하면서 [n-1][n-1]번째 인덱스의 값 중 가장 작은 값을 구한다.