Skip to content

Instantly share code, notes, and snippets.

@jsrimr
Created April 7, 2022 15:30
Show Gist options
  • Save jsrimr/d9d004a558e0eb1dca3ca31c911af040 to your computer and use it in GitHub Desktop.
Save jsrimr/d9d004a558e0eb1dca3ca31c911af040 to your computer and use it in GitHub Desktop.
https://programmers.co.kr/learn/courses/30/lessons/72415 풀라고 시도한 코드. 얼개는 짜놓았으나 이미 45분 지난 상태에서 compute_needed_move 구현하려니 도저히 안되겠어서 포기. permuation 이용하기 전에는 dfs 하려 했으나 어차피 필요한 순열 몇개 안되는 거 같아서 그냥 순열을 박아놓음
from itertools import permutations
def solution(board, r, c):
answer = float('inf')
n_set = set()
for row in board:
for el in row:
n_set.add(el)
def compute_needed_move(dst, r,c):
pass
def find_el_from_board(target, board):
loc_list = []
for i, row in enumerate(board):
for j, el in enumerate(row):
if el == target:
loc_list.append((i,j))
return loc_list
def compute_n_move(order, r, c, copied_board):
n_move = 0
for el in order:
card1_loc, card2_loc = find_el_from_board(el, copied_board)
card1_needed_move = compute_needed_move(card1_loc, r, c)
card2_needed_move = compute_needed_move(card2_loc, r, c)
if card1_needed_move <= card2_needed_move:
move1 = card1_needed_move
r,c = card1_loc
else:
move1 = card2_needed_move
r,c = card2_loc
_, move2 = compute_needed_move()
n_move += (move1 + move2 + 2)
copied_board[card1_loc] = 0
copied_board[card2_loc] = 0
return n_move
for search_order in permutations(n_set, 4):
cur_move = compute_n_move(search_order,r,c)
answer = min(answer, cur_move)
return answer
@jsrimr
Copy link
Author

jsrimr commented Apr 8, 2022

import copy
from itertools import permutations

def solution(board, r, c):
    answer = float('inf')
    n_set = set()
    for row in board:
        for el in row:
            if el > 0:
                n_set.add(el)

    def compute_needed_move(dst, r,c, board):
        target_r, target_c = dst

        # r 먼저
        r_first = 0
        if r != target_r:
            r_first +=1
            for dr in range(min(r, target_r)+1, max(r, target_r)):
                if board[dr][c] != 0:
                    r_first += 1

        if c != target_c:
            r_first +=1
            for dc in range(min(c, target_c)+1, max(c, target_c)):
                if board[target_r][dc] != 0:
                    r_first += 1

        # c 먼저
        c_first = 0
        if c!= target_c:
            c_first += 1
            for dc in range(min(c, target_c)+1, max(c, target_c)):
                if board[r][dc] != 0:
                    c_first += 1

        if r != target_r:
            c_first += 1
            for dr in range(min(r, target_r)+1, max(r, target_r)):
                if board[dr][target_c] != 0:
                    c_first += 1

        return min(r_first, c_first)

    def find_el_from_board(target, board):
        loc_list = []
        for i, row in enumerate(board):
            for j, el in enumerate(row):
                if el == target:
                    # print(el, target)
                    loc_list.append((i,j))

        # print(loc_list)
        return loc_list


    def compute_n_move(order, r, c, copied_board):
        n_move = 0
        for el in order:
            card1_loc, card2_loc = find_el_from_board(el, copied_board)

            card1_needed_move = compute_needed_move(card1_loc, r, c, copied_board)
            card2_needed_move = compute_needed_move(card2_loc, r, c, copied_board)

            if card1_needed_move <= card2_needed_move:
                move1 = card1_needed_move
                r,c = card1_loc
                other_card = card2_loc
            else:
                move1 = card2_needed_move
                r,c = card2_loc
                other_card = card1_loc

            move2 = compute_needed_move(other_card, r, c, copied_board)
            r, c= other_card

            n_move += (move1 + move2 + 2)

            copied_board[card1_loc[0]][card1_loc[1]] = 0
            copied_board[card2_loc[0]][card2_loc[1]] = 0

        return n_move

    for search_order in permutations(n_set, len(n_set)):
        cur_move = compute_n_move(search_order,r,c, copy.deepcopy(board))
        # print(cur_move)   
        answer = min(answer, cur_move)

    return answer

위에거 완성한건데 그래도 실패하는 케이스들이 있음 ㅠ

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment