문제 설명
건설회사의 설계사인 죠르디
는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.
제공된 경주로 설계 도면에 따르면 경주로 부지는 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으로 주어집니다.
풀이
구현력
과 동시에 예외 상황을 잘 파악해야 문제였습니다.
본 문제와 일반적인 최단 거리 문제의 큰 차이점은 다음과 같습니다.
1. 한 번의 이동이 항상 일정한 코스트를 지니지 않습니다
100
원 or600
원
2. 이전의 상태가 현재의 상태에 영향을 미칩니다
- 전의 자동차 방향에 따라
직선
또는코너
1번으로 인해 일반적인 그래프 완전 탐색이 아닌 다익스트라
를 이용해야 함을 알 수 있습니다. 하지만 본 문제는 보드판의 최대 크기가 25 x 25
로 압도적 작으므로, DFS
나 BFS
와 같은 완전 탐색을 이용해도 해결할 수 있습니다.
2번에서 언급된 상태는 본 문제에서 방향을 의미합니다. 즉, 자동차의 방향을 알 수 있도록 노드 안에 방향도 저장해주어야 합니다. 그리고 본 문제에서 상,하,좌,우
로 총 4
가지 방향이 존재하므로, 각각의 좌표별로도 총 4
개의 상태가 존재함을 알 수 있습니다. 예를 들어, 왼쪽 방향에서 도착한 (1,1)
과 오른쪽 방향에서 도착한 (1,1)
은 다른 상태입니다. 따라서 각 좌표별로 방향에 따른 상태를 저장할 수 있도록 배열을 확장시켜주어야 합니다.
추가적으로, 전에 왔던 방향으로 역주행하는 경우는 같은 공간에 중복 도로가 생기므로 반드시 최적이 아님을 알 수 있습니다. 또 자동차의 초기 위치가 왼쪽 끝 모서리이므로 초기 방향은 항상 오른쪽
또는 아래
임을 알 수 있습니다. 이러한 케이스들을 걸러주면 탐색 속도를 조금이나마 더 개선할 수 있습니다.
참고로 필자는 코너
의 가격을 600
원이 아닌 500
원으로 잘 못 읽어 삽질을 했습니다. 무엇보다 문제를 정확히 읽는 것이 중요합니다…
전체 코드
1 |
|