경주로 건설

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

https://tech.kakao.com/2020/07/01/2020-internship-test/

2020 카카오 인턴십 for Tech developers 문제해설

직관적으로는 시뮬레이션과 배열로 풀 수 있다.

깊이 우선 탐색(DFS)에 가지치기를 결합했다. 
이전 좌표를 남겨서 방향을 알 수 있게 했고.. 
비용 리스트를 만들어 가지치기가 가능하도록 했다. 
(의도한 건 아니고 생각의 흐름에 따라 코딩하다보니..)

def solution(board):
    costs = [[float('inf')] * len(board) for _ in range(len(board))]
    costs[0][0] = 0
    nav((0, 0), (0, 0), (len(board) - 1, len(board) - 1), board, costs)
    return costs[-1][-1]


def nav(now, prev, target, board, costs):
    if now == target:
        return
    prev_x, prev_y = prev
    x, y = now
    if y < target[1] and board[x][y + 1] == 0:
        new_cost = (100 if prev_x == x else 600) + costs[x][y]
        if new_cost <= costs[x][y + 1]:
            costs[x][y + 1] = new_cost
            nav((x, y + 1), now, target, board, costs)
    if y > 0 and board[x][y - 1] == 0:
        new_cost = (100 if prev_x == x else 600) + costs[x][y]
        if new_cost <= costs[x][y - 1]:
            costs[x][y - 1] = new_cost
            nav((x, y - 1), now, target, board, costs)
    if x < target[0] and board[x + 1][y] == 0:
        new_cost = (100 if prev_y == y else 600) + costs[x][y]
        if new_cost <= costs[x + 1][y]:
            costs[x + 1][y] = new_cost
            nav((x + 1, y), now, target, board, costs)
    if x > 0 and board[x - 1][y] == 0:
        new_cost = (100 if prev_y == y else 600) + costs[x][y]
        if new_cost <= costs[x - 1][y]:
            costs[x - 1][y] = new_cost
            nav((x - 1, y), now, target, board, costs)
    return

테스트 1 〉	통과 (0.03ms, 9.6MB)
테스트 2 〉	통과 (0.02ms, 9.62MB)
테스트 3 〉	통과 (0.03ms, 9.71MB)
테스트 4 〉	통과 (0.05ms, 9.85MB)
테스트 5 〉	통과 (0.05ms, 9.68MB)
테스트 6 〉	통과 (2.78ms, 9.75MB)
테스트 7 〉	통과 (3.44ms, 9.71MB)
테스트 8 〉	통과 (3.27ms, 9.66MB)
테스트 9 〉	통과 (1.79ms, 9.79MB)
테스트 10 〉	통과 (2.25ms, 9.68MB)
테스트 11 〉	통과 (163.32ms, 9.68MB)
테스트 12 〉	통과 (193.70ms, 9.91MB)
테스트 13 〉	통과 (0.37ms, 9.83MB)
테스트 14 〉	통과 (1.34ms, 9.79MB)
테스트 15 〉	통과 (5.93ms, 9.71MB)
테스트 16 〉	통과 (17.65ms, 9.7MB)
테스트 17 〉	통과 (30.14ms, 9.63MB)
테스트 18 〉	통과 (59.91ms, 9.65MB)
테스트 19 〉	통과 (166.13ms, 9.72MB)
테스트 20 〉	통과 (1.43ms, 9.76MB)
테스트 21 〉	통과 (1.11ms, 9.67MB)
테스트 22 〉	통과 (0.13ms, 9.71MB)
테스트 23 〉	통과 (0.11ms, 9.66MB)

좀 줄인다면... 

def solution(board):
    costs = [[float('inf')] * len(board) for _ in range(len(board))]
    costs[0][0] = 0
    nav((0, 0), (0, 0), len(board) - 1, board, costs)
    return costs[-1][-1]


def nav(now, prev, target, board, costs):
    if target == now[0] == now[1]:
        return
    (x, y), (px, py) = now, prev
    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nx, ny = x + dx, y + dy
        if 0 <= nx <= target and 0 <= ny <= target:
            if board[nx][ny] == 0:
                new_cost = costs[x][y] + (100 if x - px == nx - x or y - py == ny - y else 600)
                if new_cost <= costs[nx][ny]:
                    costs[nx][ny] = new_cost
                    nav((nx, ny), now, target, board, costs)
    return

중첩된 if 문은 가독성이 좋지 않기 때문에 실전에선...

테스트 1 〉	통과 (0.04ms, 9.59MB)
테스트 2 〉	통과 (0.02ms, 9.52MB)
테스트 3 〉	통과 (0.02ms, 9.75MB)
테스트 4 〉	통과 (0.06ms, 9.68MB)
테스트 5 〉	통과 (0.06ms, 9.6MB)
테스트 6 〉	통과 (4.39ms, 9.67MB)
테스트 7 〉	통과 (4.71ms, 9.77MB)
테스트 8 〉	통과 (4.15ms, 9.56MB)
테스트 9 〉	통과 (2.17ms, 9.6MB)
테스트 10 〉	통과 (2.33ms, 9.62MB)
테스트 11 〉	통과 (150.64ms, 9.64MB)
테스트 12 〉	통과 (352.56ms, 10.1MB)
테스트 13 〉	통과 (0.30ms, 9.57MB)
테스트 14 〉	통과 (1.18ms, 9.52MB)
테스트 15 〉	통과 (9.10ms, 9.64MB)
테스트 16 〉	통과 (30.11ms, 9.8MB)
테스트 17 〉	통과 (24.30ms, 9.6MB)
테스트 18 〉	통과 (141.67ms, 9.66MB)
테스트 19 〉	통과 (293.59ms, 9.7MB)
테스트 20 〉	통과 (2.09ms, 9.75MB)
테스트 21 〉	통과 (4.30ms, 9.74MB)
테스트 22 〉	통과 (0.14ms, 9.56MB)
테스트 23 〉	통과 (0.14ms, 9.61MB)

이건 실패.. ㅠ,.ㅠ 

def solution(board):
    length = len(board)
    costs = [[float('inf')] * length for _ in range(length)]
    costs[0][0] = 0
    stack = [(0, 0, 0, 0)]
    while stack:
        x, y, px, py = stack.pop()
        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < length and 0 <= ny < length:
                if board[nx][ny] == 0:
                    new_cost = costs[x][y] + (100 if x - px == nx - x or y - py == ny - y else 600)
                    if new_cost <= costs[nx][ny]:
                        costs[nx][ny] = new_cost
                        stack.append((nx, ny, x, y))
    return costs[-1][-1]


# 테스트 14 〉	실패 (0.78ms, 9.59MB)


def solution(board):
    length = len(board)
    costs = [[float('inf')] * length for _ in range(length)]
    costs[0][0] = 0
    stack = [(0, 0, 0, 0, 0)]
    while stack:
        x, y, px, py, p_cost = stack.pop()
        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < length and 0 <= ny < length:
                if board[nx][ny] == 0:
                    new_cost = p_cost + (100 if x - px == nx - x or y - py == ny - y else 600)
                    if new_cost <= costs[nx][ny]:
                        costs[nx][ny] = new_cost
                        stack.append((nx, ny, x, y, new_cost))
    return costs[-1][-1]
    
    
# 테스트 14 〉	실패 (0.78ms, 9.59MB)

일반적으로 깊이 우선 탐색 보다는
너비 우선 탐색이 시간적으로 이익인 경우가 많아서... 
너비 우선 탐색으로도 풀어보자. 

개인적으론 깊이 우선 탐색이 직관적으로 느껴져..
깊이 우선 탐색으로 먼저 풀어보는 습관이 있다... 

너비 우선 탐색은 큐를 이용하는 경우가 많은데...

재귀(깊이 우선 탐색)를 이용하면 이전의 x, y 좌표만 기억해두면 ...
꼬리에 꼬리를 물기 때문에 방향의 처리가 간편한데.. 
너비 우선 탐색에서는 조금 더 복잡하다. 

def solution(board):
    from collections import deque
    length = len(board)
    costs = [[float('inf')] * length for _ in range(length)]
    costs[0][0] = 0
    que = deque([(0, 0, 0, 0, 0)])
    while que:
        x, y, px, py, prev_cost = que.popleft()
        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < length and 0 <= ny < length:
                if board[nx][ny] == 0:
                    new_cost = prev_cost + (100 if x - px == nx - x or y - py == ny - y else 600)
                    if new_cost <= costs[nx][ny]:
                        costs[nx][ny] = new_cost
                        que.append((nx, ny, x, y, new_cost))
    return costs[-1][-1]

테스트 1 〉	통과 (0.05ms, 9.78MB)
테스트 2 〉	통과 (0.03ms, 9.57MB)
테스트 3 〉	통과 (0.03ms, 9.69MB)
테스트 4 〉	통과 (0.05ms, 9.6MB)
테스트 5 〉	통과 (0.06ms, 9.6MB)
테스트 6 〉	통과 (1.35ms, 9.68MB)
테스트 7 〉	통과 (1.49ms, 9.61MB)
테스트 8 〉	통과 (1.74ms, 9.66MB)
테스트 9 〉	통과 (0.37ms, 9.57MB)
테스트 10 〉	통과 (1.09ms, 9.73MB)
테스트 11 〉	통과 (47.78ms, 9.75MB)
테스트 12 〉	통과 (3.84ms, 9.61MB)
테스트 13 〉	통과 (0.27ms, 9.65MB)
테스트 14 〉	통과 (0.61ms, 9.66MB)
테스트 15 〉	통과 (1.53ms, 9.64MB)
테스트 16 〉	통과 (3.39ms, 9.65MB)
테스트 17 〉	통과 (9.11ms, 9.61MB)
테스트 18 〉	통과 (12.37ms, 9.59MB)
테스트 19 〉	통과 (48.26ms, 9.77MB)
테스트 20 〉	통과 (1.47ms, 9.6MB)
테스트 21 〉	통과 (1.26ms, 9.58MB)
테스트 22 〉	통과 (0.09ms, 9.58MB)
테스트 23 〉	통과 (0.10ms, 9.78MB)

방향 개념을 도입하여... 

def solution(board):
    from collections import deque
    length = len(board)
    costs = [[float('inf')] * length for _ in range(length)]
    costs[0][0] = 0
    que = deque(((0, 0, 0, 0), (0, 0, 0, 1)))
    while que:
        px, py, prev_cost, prev_direction = que.popleft()
        for direction, (dx, dy) in enumerate(((0, 1), (1, 0), (0, -1), (-1, 0))):
            x, y = px + dx, py + dy
            if 0 <= x < length and 0 <= y < length:
                if board[x][y] == 0:
                    if abs(direction - prev_direction) != 2:
                        cost = prev_cost + (100 if direction == prev_direction else 600)
                        if cost <= costs[x][y]:
                            costs[x][y] = cost
                            que.append((x, y, cost, direction))
    return costs[-1][-1]

테스트 1 〉	통과 (0.06ms, 9.57MB)
테스트 2 〉	통과 (0.04ms, 9.59MB)
테스트 3 〉	통과 (0.04ms, 9.64MB)
테스트 4 〉	통과 (0.07ms, 9.66MB)
테스트 5 〉	통과 (0.10ms, 9.62MB)
테스트 6 〉	통과 (1.72ms, 9.57MB)
테스트 7 〉	통과 (1.29ms, 9.64MB)
테스트 8 〉	통과 (1.50ms, 9.66MB)
테스트 9 〉	통과 (0.73ms, 9.66MB)
테스트 10 〉	통과 (1.43ms, 9.67MB)
테스트 11 〉	통과 (56.29ms, 9.66MB)
테스트 12 〉	통과 (2.76ms, 9.8MB)
테스트 13 〉	통과 (0.46ms, 9.64MB)
테스트 14 〉	통과 (0.61ms, 9.66MB)
테스트 15 〉	통과 (1.75ms, 9.82MB)
테스트 16 〉	통과 (5.06ms, 9.63MB)
테스트 17 〉	통과 (9.58ms, 9.73MB)
테스트 18 〉	통과 (13.57ms, 9.61MB)
테스트 19 〉	통과 (51.06ms, 9.7MB)
테스트 20 〉	통과 (1.52ms, 9.79MB)
테스트 21 〉	통과 (1.32ms, 9.81MB)
테스트 22 〉	통과 (0.15ms, 9.64MB)
테스트 23 〉	통과 (0.13ms, 9.51MB)

메모리를 아끼고 싶으면 board의 1을 전부 False로 바꾼다던지 하고..
costs를 쓰지 않는 방법도 있겠지만..