23.03.21 파이썬 코딩 퀴즈#201 경주로 건설 (프로그래머스 스쿨)

이번 문제는 경주로 건설 문제이다.

전달받은 NxN 배열을 이용해서 (0,0)부터 (N-1,N-1) 까지 도로를 건설해야 한다.

이 때, 인접한 두 칸(상하, 좌우)를 연결하는 도로를 직선 도로라고 하며, 100원이 소요된다.

그리고 두 직선 도로를 직각으로 만나는 지점을 코너라고 하며, 500원이 소요된다.

이 때 경주로를 건설하는데 필요한 최소 비용을 계산해야 한다.

예를 들어 3X3 배열의 모든 블럭이 비어있는 상태라면 어떻게든 도로를 건설하는게 가능하다.

위 그림처럼 도로를 건설하면 총 4개의 코너와 6개의 직선도로가 생성되며, 건설 비용은 2600원이다.

하지만 위 그림처럼 직각으로 설치해 버리면 직선도로 4개와 코너 1개만 설치하면 된다. 건설 비용은 900원으로 최소이다.

제한 사항에 의해 경주로를 건설하지 못하는 경우는 주어지지 않는다.

 

문제가 최단거리 미로찾기의 변형처럼 느껴진다.

처음 작성한 코드는 위와 같다.

사실 처음은 아니고... 하루종일 수정에 수정을 반복하다가, 분기점으로 남길 필요가 있어서 위 코드를 가져왔다.

전달받은 board를 확장시킨 new_board 와 각 구간의 최소 비용을 계산한 cost_board 두가지를 준비하였다.

그리고 확장된 new_board를 기준으로 탐색하기 때문에 시작 위치는 (1,1)이 된다.

반복문에 의해 다음으로 이동할 좌표 (nx, ny)를 돌게 되는데, 이때 사용할 i 값에 따라 방향이 결정된다.

처음 설정한 d 값은 -1 이고, 이 d 값이 i 값과 같거나, -1 인 경우에는 같은 방향의 도로로 간주한다.

쉽게 생각해서 (1,1) 의 d 값은 -1 이고 이때 탐색에 의해 생성된 nx, ny 는 항상 i 값을 d 값으로 사용하게 된다.

즉 같은 방향으로 이동하는 좌표들은 같은 d 값을 가지게 된다. 

위 코드에서는 d == 0 == 오른쪽 이동, d==1==아래로 이동, d==2==왼쪽으로 이동, d==3==위쪽으로 이동이다.

해당 i값에 의해 cost 를 계산해주고, (nx,ny)에 처음 방문한게 아니라면, 새로운 cost 비용과 기존 값을 비교하면 더 작은값으로 갱신해 주고, 다시 한번 해당 좌표를 q에 넣어주었다.

방문확인용 리스트를 쓰지 않은 경우는 이렇게 중복되는 값을 다시 최소값으로 갱신시켜 주기 위함이다.

해당 코드로 테케를 돌렸는데 정확하게 25번 테케에서 막힌다. 

문제는 위 주황색 구간이다.

노란색 도로를 따라서 건설하면 주황색 구간은 2800 -> 2900이 된다.

하지만 녹색 도로를 따라서 건설하면 2700 -> 3300이 된다.

처음 건설되는 비용은 녹색 도로가 싸지만, 그 다음 구간에 건설되는 비용은 노란색 도로가 싸다.

즉 교차하는 지점은 분명 녹색 도로가 더 싸지만, 그 이후구간 부터는 노란색 도로가 더 저렴한 것을 알 수 있다.

즉, 교차지점 뿐만 아니라 그 이후의 도로에 대해서도 생각해야 한다.

그렇게 작성한 두번째 코드, 처음 작성한 코드에서 cost_board[x][y]값을 배열로 저장하게 만들었다. 이로써 들어온 방향에 따라 cost_board는 값을 따로 가지게 된다. 그리고 다시 테케 11번에서 시간제한에 걸렸다...

아마도 매번 ocst_board[x][y]의 값을 배열로 만들고, 그 값을 확인하고 전달하는 과정에서 시간 소요가 많은것 같다.

그렇게 돌고돌아 다시 첫번째 코드로 돌아왔다....

첫번째 코드에서 문제가 되었던 지점은 바로 교차점이다. 그 교차점만 해결해주면 문제될 게 없다.

그리고 든 생각은 다음에 건설할 도로의 값까지 같이 비교해 주면 문제가 해결되지 않을까?

그렇게 코드에 딱 한줄을 더 추가해 주었다.

첫번째 코드를 실행하였을때, 저 붉은 셀 부분의 계산에서, 정확히 발하면 그 바로 위 값인 2700 과 2800 이후의 계산이 불가했다. 그리고 두 값의 차는 정확히 400이 난다.

왼쪽에서 들어오는 길 A(녹색)을 2700 값을 기준으로 보면 직선(100)으로 받아서 커브(600)로 나가게 된다.

오른쪽에서 들어오는 길 B(노란색)을 2800 값을 기준으로 보면 직선(100)으로 받아서 직선(100)으로 나가게 된다.

즉 값의 차가 500이 발생한다.

이는 새롭게 구한 cost-500 이 기존 값보다 작다면 다른 결과를, 같거나 크다면 기존 값으로 건설하는게 더 나은 결과임을 보여준다.