2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기 (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
from itertools import permutations
from collections import deque

def ctrl(board, x0, y0, dx, dy):
    for i in range(1, 4):
        if 0 <= (x1 := x0 + dx * i) < 4 and 0 <= (y1 := y0 + dy * i) < 4:
            if board[x1][y1] > 0:
                return (x1, y1)
            l = i
    return (x0 + dx * l, y0 + dy * l)

def move(board, xy0, xy1):
    dist = [[6] * 4 for _ in range(4)]
    q = deque([(xy0, 0)])
    while q:
        [x, y], d = q.popleft()
        if d < dist[x][y]:
            dist[x][y] = d
            for dx, dy in [(+1, 0), (-1, 0), (0, +1), (0, -1)]:
                if 0 <= x + dx < 4 and 0 <= y + dy < 4:
                    q.append(((x + dx, y + dy), d + 1))
                    q.append((ctrl(board, x, y, dx, dy), d + 1))
    return dist[xy1[0]][xy1[1]]

def solution(board, r, c):
    loc = {k: [] for k in range(1, 7)}
    for i in range(4):
        for j in range(4):
            if board[i][j]:
                loc[board[i][j]].append((i, j))
    minv = 100
    for p in permutations(filter(lambda v: v, loc.values())):
        sumv = 0
        xys = [(r, c)]
        stage = [[v for v in w] for w in board]
        for xy1, xy2 in p:
            vs = [(move(stage, xy, xy1) + move(stage, xy1, xy2), xy2) for xy in xys]\
               + [(move(stage, xy, xy2) + move(stage, xy2, xy1), xy1) for xy in xys]
            stage[xy1[0]][xy1[1]] = stage[xy2[0]][xy2[1]] = 0
            sumv += 2 + (mvn := min(vs)[0])
            xys = [xy for m, xy in vs if m == mvn]
        minv = min(sumv, minv)
    return minv

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
def solution(board, r, c):
    board = [[{'id': e, 'act': e>0} for e in row] for row in board]

    def dist(src, dst):
        (r1, c1), (r2, c2) = src, dst

        if r2 == r1 and c2 == c1:
            return 0
        elif r2 == r1 or c2 == c1:
            return 1
        elif (r1, c1) in [(0, 0), (0, 3), (3, 0), (3, 3)] and (abs(r2 - r1) == 2 and abs(c2 - c1) == 2):
            if board[r1][c2]['act'] or board[r2][c1]['act']:
                return 2
            else:
                return 3
        else:
            return 2
    def enter(dst):
        r, c = dst
        if board[r][c]['act']:
            return True
        else:
            return False

    answer = 0

    chars = []
    for idx_r, row in enumerate(board):
        for idx_c, elem in enumerate(row):
            if elem['id'] > 0:
                chars.append([(idx_r, idx_c), elem])

    # 1. cur -> nearest character
    first_card = True
    cur = (r, c)
    while sum(ch[1]['act'] for ch in chars):
        min_d = 10
        for ch in chars:
            if first_card:
                cond = ch[1]['act']
            else:
                cond = ch[1]['act'] and (ch[0] != cur) and (ch[1]['id'] == selected_id)
            if cond:
                if (d := dist(cur, ch[0])) < min_d:
                    min_d = d
                    dst, stat = ch

        ent = enter(dst)
        if not first_card:
            board[cur[0]][cur[1]]['act'] = board[dst[0]][dst[1]]['act'] = False

        answer += min_d+1 if ent else min_d
        # print(f"{cur} -> {dst} (answer: {answer})")

        cur = dst
        if first_card:
            selected_id = stat['id']
        first_card = False if first_card else True

    return answer