문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/72415


로직은

없앨 카드 번호 순서를 정하고

각 순서에 따라 그 번호의 카드를 없앨때 비용을 계산하는 식으로 완전탐색했어요




from itertools import permutations

from collections import deque

from copy import deepcopy

def vaild(x,y):#영역을 벗어나는지 확인하는 함수

    if x < 0 or x> 3 or y < 0 or y > 3:

        return False

    return True

def min_cost(board,sx,sy,dx,dy):#s -> d까지 갈때의 최소비용을 구하는 함수

    if sx == dx and sy == dy:

        return 0

    fee = [[10000000]*4 for _ in range(4)]#키 누르는 횟수를 저장할 2차원리스트

    q = deque([(sx,sy)])

    fee[sy][sx] = 0

    while q:

        x,y = q.popleft()

        for x1,y1 in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:#인접한 영역

            if vaild(x1,y1) and fee[y1][x1] > fee[y][x] + 1:

                fee[y1][x1] = fee[y][x] + 1

                q.append((x1,y1))

                if y1 == dy and x1 == dx:

                    return fee[dy][dx]

        for x1,y1 in [(1,0),(-1,0),(0,1),(0,-1)]:#ctrl을 누르는 영역

            tx,ty = x,y

            while True:

                tx += x1

                ty += y1

                if not vaild(tx,ty):#해당 방향의 맨끝으로

                    tx -= x1

                    ty -= y1

                    if fee[ty][tx] > fee[y][x] + 1:

                        fee[ty][tx] = fee[y][x] + 1

                        q.append((ty,tx))

                        if ty == dy and tx == dx:

                            return fee[dy][dx]

                    break

                if board[ty][tx] != 0:

                    if fee[ty][tx] > fee[y][x] + 1:#카드위치로

                        fee[ty][tx] = fee[y][x] + 1

                        q.append((ty,tx))

                        if ty == dy and tx == dx:

                            return fee[dy][dx]

                    break

    return fee[dy][dx] #목적지까지 가는 최소 비용 리턴

def brute_f(board,e,idx,cost,cx,cy,gx,gy,dx,dy,arr):

    if arr and min(arr) <= cost:

        return

    b = deepcopy(board)

    c = min_cost(b,cx,cy,gx,gy) + min_cost(b,gx,gy,dx,dy) + 2

    cnt = c + cost

    p1,p2 = e[idx]

    x1,y1 = p1

    x2,y2 = p2

    b[y1][x1] = 0

    b[y2][x2] = 0

    nxt = idx + 1

    if nxt >= len(e):

        arr.add(cnt)

        return

    n1,n2 = e[nxt]

    nx1,ny1 = n1

    nx2,ny2 = n2

    brute_f(b,e,nxt,cnt,dx,dy,nx1,ny1,nx2,ny2,arr)

    brute_f(b,e,nxt,cnt,dx,dy,nx2,ny2,nx1,ny1,arr)

def solution(board, r, c):

    dic = {}

    for y in range(4):

        for x in range(4):

            if board[y][x] != 0:

                if board[y][x] not in dic:

                    dic[board[y][x]] = [(x,y)]

                else:

                    dic[board[y][x]].append((x,y))

    data = list(permutations(dic.values(),len(dic))) #각 카드의 좌표를 묶고 순열로 돌림

    counts = set([])

    for e in data:

        i1,i2 = e[0]

        brute_f(board,e,0,0,c,r,i1[0],i1[1],i2[0],i2[1],counts)

        brute_f(board,e,0,0,c,r,i2[0],i2[1],i1[0],i1[1],counts)

    return min(counts)