[파이썬 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원이 추가로 듭니다.
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.

예를 들어, 아래 그림은 직선 도로 6개와 코너 4개로 구성된 임의의 경주로 예시이며, 건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.

또 다른 예로, 아래 그림은 직선 도로 4개와 코너 1개로 구성된 경주로이며, 건설 비용은 4 x 100 + 1 x 500 = 900원 입니다.

---

도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
• board 배열의 각 원소의 값은 0 또는 1 입니다.
  • 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
  • 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
• board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
• 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

---

입출력 예

boardresult

[[0,0,0],[0,0,0],[0,0,0]]	900
[[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]]	3800
[[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]]	2100
[[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0]]	3200

입출력 예에 대한 설명

입출력 예 #1

본문의 예시와 같습니다.

입출력 예 #2

위와 같이 경주로를 건설하면 직선 도로 18개, 코너 4개로 총 3800원이 듭니다.

입출력 예 #3

위와 같이 경주로를 건설하면 직선 도로 6개, 코너 3개로 총 2100원이 듭니다.

입출력 예 #4

붉은색 경로와 같이 경주로를 건설하면 직선 도로 12개, 코너 4개로 총 3200원이 듭니다.
만약, 파란색 경로와 같이 경주로를 건설한다면 직선 도로 10개, 코너 5개로 총 3500원이 들며, 더 많은 비용이 듭니다.

---

import collections
x_move = [1,0,-1,0]
y_move = [0,1,0,-1]
MAX = 987654321
answer = MAX

def bfs(board):
    global answer
    # 최소비용을 기록하는 3차원 리스트 만듬. 처음엔 최댓값. [x축][y축][방향(밑,오른쪽,위,왼쪽 순서로)]
    visited = [[[MAX for y in range(len(board))] for x in range(len(board))] for z in range(4)]
    q = collections.deque()
    # [x, y, cost, dir]
    # dir -> 밑,오른쪽,위,왼쪽 -> 0,1,2,3
    # 0행0열 초기화
    for z in range(4):
        visited[z][0][0]= 0
    # 0행1열 초기화
    if board[0][1] != 1:
        q.append([0,1,100,1])
        visited[1][0][1] = 100
    # 1행0열 초기화
    if board[1][0] != 1:
        q.append([1,0,100,0])
        visited[0][1][0] = 100
    
    while q:
    	# x축, y축, 비용, 방향
        x, y, cost, dir = q.pop()
        
        for i in range(4):
        	# 다음에 이동할 x축 y축
            n_x = x + x_move[i]
            n_y = y + y_move[i]
            
            # 현재 방향과 다음에 이동할 방향이 틀리다면 +600원
            if dir != i:
                n_cost = cost + 600
            # 같다면 +100원
            else:
                n_cost = cost + 100
            
            #범위 안에 있고
            if 0 <= n_x < len(board) and 0 <= n_y < len(board):
                # 다음에 갈 곳이 벽도 아니며
                if board[n_x][n_y] != 1:
                	# 해당 [방향][x축][y축]에 기록되어있는 것보다 현재 비용이 작다면, 큐에 넣고 바꿔줌
                    if visited[i][n_x][n_y] > n_cost:
                        q.append([n_x, n_y, n_cost, i])
                        visited[i][n_x][n_y] = n_cost
    # x축y축 끝의 4방향 중에서 최솟값을 찾는다.
    for z in range(4):
        if answer > visited[z][len(board)-1][len(board)-1]:
            answer = visited[z][len(board)-1][len(board)-1] 
    return answer


def solution(board):
    return bfs(board)

 

정확성  테스트
테스트 1 〉	통과 (0.10ms, 10.3MB)
테스트 2 〉	통과 (0.05ms, 10.3MB)
테스트 3 〉	통과 (0.05ms, 10.3MB)
테스트 4 〉	통과 (0.15ms, 10.3MB)
테스트 5 〉	통과 (0.17ms, 10.3MB)
테스트 6 〉	통과 (8.29ms, 10.3MB)
테스트 7 〉	통과 (9.72ms, 10.3MB)
테스트 8 〉	통과 (8.10ms, 10.3MB)
테스트 9 〉	통과 (8.18ms, 10.3MB)
테스트 10 〉	통과 (4.84ms, 10.3MB)
테스트 11 〉	통과 (252.05ms, 10.3MB)
테스트 12 〉	통과 (789.24ms, 10.3MB)
테스트 13 〉	통과 (1.34ms, 10.3MB)
테스트 14 〉	통과 (2.64ms, 10.3MB)
테스트 15 〉	통과 (30.15ms, 10.3MB)
테스트 16 〉	통과 (95.85ms, 10.3MB)
테스트 17 〉	통과 (149.29ms, 10.3MB)
테스트 18 〉	통과 (259.87ms, 10.4MB)
테스트 19 〉	통과 (170.18ms, 10.4MB)
테스트 20 〉	통과 (4.91ms, 10.4MB)
테스트 21 〉	통과 (2.07ms, 10.3MB)
테스트 22 〉	통과 (0.33ms, 10.3MB)
테스트 23 〉	통과 (0.22ms, 10.2MB)
테스트 24 〉	통과 (0.30ms, 10.3MB)

 

후기

 bfs 문제다!(dfs 등으로 풀 수도 있었겠지만 bfs를 가장 선호함으로...) 

 일반적인 bfs문제가 최단거리지만, 이것은 최소비용을 찾아내는 문제다. 

 2차원 리스트로 풀다가 계속 1개가 틀리고, 뭔가 이상한 것도 있길래 3차원 리스트로 다시 풀었다.

 물론 진짜 코테였으면 시간이 너무 소모되서 망했을듯 싶다.

 

풀이

* 2차원 리스트가 아닌 3차원 리스트로 풀어야 한다. 2차원 리스트를 사용해서 단순히 최솟값이 작다고 변경해주면 예상치 못한 오류가 나온다. 아래 그림을 보면,  3500(오른쪽)대신에 3400원(밑방향)이 쩜에서 선택된다. 그런데 이런 '방향의 차이' 때문에 끝에서는 알맞는 답이 안나온다. 3500(오른쪽)은 끝에서는 3500+100=3600원인데 3400(밑방향)은 끝에서 3400+600=4000원이다.

 * 때문에 2차원 리스트를 사용하는 것은 한계가 있다. 3차원 리스트를 사용하여 [방향4개][x축][y축]를 저장한다고 생각하면, 쩜에서는 [오른쪽방향][쩜x축][쩜y축] = 3500 과 동시에 [밑방향][쩜x축][쩜y축] = 3400이 저장된다. 끝에서는 [오른쪽방향][끝x축][끝y축] = 3600,  [밑방향][끝x축][끝y축] = 4000이 저장된다. 끝 x축y축의 방향을 전부 탐색해서 가장 적은 것이 최솟값이라고 할 수 있다.

 

(1) 위치별 최솟값을 저장하는 visited 3차원 리스트를 생성한다. [방향], [x축,] [y축] 으로 설정한다. (초기값은 최대값으로 한다.)

(참고로 python은 [[[y축] x축] z축] 방식으로 3차원 리스트를 생성하면, 요소를 가져올때 [z축][x축][y축] 이다. 처음 알았다. 헷갈린다)

(2) 시작위치, 시작위치의 바로 오른쪽, 시작위치의 바로 아래쪽을 초기에 설정하였다. 해당 위치가 벽이 아니라면, 큐에 해당하는x축, 해당하는y축, 비용(100원),방향(각각 오른쪽 아래쪽) 을 알맞게 넣어준다. visited도 100원씩 넣어준다.

(3) 큐에서 pop해주고, 현재 위치에 해당하는 x축 y축 비용 방향을 가져온다.

(4) 현재 위치에서 다음으로 갈 곳을 찾는다. 상하좌우를 탐색한다.

(5) 현재 방향과 다음으로 갈 곳 방향이 같다면 다음 비용은 +600원, 방향이 다르다면 다음 비용은 +100원을 해줘야 한다.

(6) 다음 x축 y축 (다음으로 갈 곳)이 범위를 벗어나지 않고, 벽도 아니며, 해당 [방향][x축][y축]에 기록되어있는 것보다 다음 비용이 작다면, 다음으로 갈 곳이 맞다!  큐에 넣음과 동시에 visited(방향별 x축 y축의 최솟값)를 바꿔준다.

(7) bfs가 끝나면 [방향(상하좌우)][끝x축][끝y축] 을 탐색하고, 가장 작은 값이 정답이다.