2020 카카오 인턴십 - 경주로 건설 (Level 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
from collections import deque

def solution(board):
    def get_position(cur_v, next_v):
        cur_x, cur_y   = cur_v
        next_x, next_y = next_v
        if cur_x - next_x == -1:   # (0, 0) -> (1, 0)
            return 1
        elif cur_y - next_y == 1:  # (0, 1) -> (0, 0)
            return 2
        elif cur_x - next_x == 1:  # (1, 0) -> (0, 0)
            return 3
        else:                      # (0, 0) -> (0, 1)
            return 4
    def get_neighbors(x, y, n):
        rst = []
        for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            nx, ny = x+dx, y+dy
            if (0 <= nx <= n-1) and (0 <= ny <= n-1) and (board[nx][ny] == 0):
                rst.append(((nx, ny), get_position((x, y), (nx, ny))))
        return rst
    def get_cost(paths):
        if len(paths) < 3:
            return 100
        v1, v2, v3 = paths[-3:]
        if (v1[0]+v3[0])/2 % 1 != 0:
            return 500 + 100
        else:
            return 100

    n   = len(board)
    src = (0, 0)
    q   = deque([src])

    paths_pos = {src: {0: [src]}}  # paths_pos[(x, y)]: {pos: pos로 (x, y)까지 도달하는 최단비용거리}
    costs_pos = {src: {0: 0}}      # costs_pos[(x, y)]: {pos: pos로 (x, y)까지 도달하는 최단비용}
    while q:
        cur_v = q.popleft()
        for next_v, pos in get_neighbors(*cur_v, n):
            opt_pos   = min(costs_pos[cur_v], key=lambda pos: costs_pos[cur_v][pos])
            next_path = paths_pos[cur_v][opt_pos] + [next_v]
            next_cost = costs_pos[cur_v][opt_pos] + get_cost(next_path)

            if (len(next_path) >= 3) and (next_path[-3] == next_path[-1]):  # 왔던 길
                continue
            if (next_v in costs_pos) and (pos in costs_pos[next_v]) and (costs_pos[next_v][pos] <= next_cost):
                continue
            if next_v not in paths_pos:
                paths_pos[next_v] = {}
                costs_pos[next_v] = {}
            paths_pos[next_v][pos], costs_pos[next_v][pos] = next_path, next_cost
            q.append(next_v)
            # print(next_v, pos, '->', next_path, next_cost)

    q   = deque([src])

    paths_pos = {src: {0: [src]}}  # paths_pos[(x, y)]: {pos: pos로 (x, y)까지 도달하는 최단비용거리}
    costs_pos = {src: {0: 0}}      # costs_pos[(x, y)]: {pos: pos로 (x, y)까지 도달하는 최단비용}
    while q:
        cur_v = q.popleft()
        for next_v, pos in get_neighbors(*cur_v, n):
            opt_pos   = min(costs_pos[cur_v], key=lambda pos: costs_pos[cur_v][pos] + get_cost(paths_pos[cur_v][pos] + [next_v]))
            next_path = paths_pos[cur_v][opt_pos] + [next_v]
            next_cost = costs_pos[cur_v][opt_pos] + get_cost(next_path)

            if (len(next_path) >= 3) and (next_path[-3] == next_path[-1]):  # 왔던 길
                continue
            if (next_v in costs_pos) and (pos in costs_pos[next_v]) and (costs_pos[next_v][pos] <= next_cost):
                continue
            if next_v not in paths_pos:
                paths_pos[next_v] = {}
                costs_pos[next_v] = {}
            paths_pos[next_v][pos], costs_pos[next_v][pos] = next_path, next_cost
            q.append(next_v)
            # print(next_v, pos, '->', next_path, next_cost)

    return min(costs_pos[(n-1, n-1)].values())