2021 카카오 코테 카드 짝 맞추기 풀다가 막혔는데 질문좀

PS 갤러리
마이너

알고리즘 문제를 해결하는 Problem Solving을 다루는 갤러리입니다.

매니저

캐티(tae826)

부매니저

부재중입니다.(ailedear) Gravekper(gravekpe…) 옥토끼(moonrabb…) 나는최고(mebest)

개설일

2018-05-28

[질문] 2021 카카오 코테 카드 짝 맞추기 풀다가 막혔는데 질문좀

ㅇㅇ(125.131) 2021.02.23 01:15:49

조회 383 추천 0 댓글 3

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

일단 이거구요

from queue import PriorityQueue as pq
from copy import deepcopy

def solution(board, r, c):
    answer = 10**6
    SIZE = 4
    DELTAS = ((1, 0), (0, 1), (-1, 0), (0, -1))
    
    def _is_in_range(r, c):
        return 0 <= r < SIZE and 0 <= c < SIZE
    def _is_empty(r, c, bd):
        return bd[r][c] == 0
    def _yield_moves(d, r, c, bd):
        for dr, dc in DELTAS:
            nr = r + dr
            nc = c + dc
            if not _is_in_range(nr, nc):
                continue
            yield(d+1, nr, nc)
            while _is_empty(nr, nc, bd) and _is_in_range(nr+dr, nc+dc):
                nr = nr + dr
                nc = nc + dc
            yield(d+1, nr, nc)
            
    def go(r, c, nr, nc, bd):
        q = pq()
        q.put((0, r, c))
        visited = set()
        visited.add((0, r, c))
        
        while q.queue:
            d, r, c = q.get()
            if (r, c) == (nr, nc):
                return d
            for next_cursor in _yield_moves(d, r, c, bd):
                if next_cursor not in visited:
                    q.put(next_cursor)
                    visited.add(next_cursor)
        return 0

    cand = []
    for i, arr in enumerate(board):
        for j, val in enumerate(arr):
            if val != 0:
                cand.append((val, i, j))

    l = len(cand)
    used = [0] * l
    def back(chosen, board, moves):
        nonlocal answer
        if len(chosen) == l:
            x, y = r, c
            moves = 0
            m = []
            bd = deepcopy(board)
            for card, j, k in chosen:
                moves += go(x, y, j, k, bd)
                bd[x][y] = 0
                x, y = j, k
            answer = min(answer, moves+l)
            
            return
        for i in range(l):
            if not used[i]:
                if len(chosen)%2 ==0 or (chosen and chosen[-1][0] == cand[i][0]):
                    chosen.append(cand[i])
                    used[i] = 1
                    back(chosen, board, moves)
                    used[i] = 0
                    chosen.pop()
        return
        
    back([], board, 0)
    return answer

    
print(solution([[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]], 1, 0), 14)
print(solution([[3, 0, 0, 2], [0, 0, 1, 0], [0, 1, 0, 0], [2, 0, 0, 3]], 0, 1), 16)

코드는 이렇구요

설명하면

카드 AABBCC있으면

A1A2B1B2C1C2부터

A2A1B1B2C1C2 ... C2C1B2B1A2A1이렇게 모든 경우 찾아서 경로별로 최단거리를 구했음

어디서 시간을 잡아먹는지 좀 알려주세요

시간초과가 뜸

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2864	설문	비난 여론에도 뻔뻔하게 잘 살 것 같은 스타는?	운영자	24/06/03	-	-
44906	공지	피갤컵 call for tasks를 진행합니다! [7]	*나는최고*	24.05.22	668	16
44466	공지	[ps 정보글 모음집] [2]	*나는최고*	24.05.07	761	12
44058	공지	알고리즘 대회 공부 과정 [22]	*나는최고*	24.04.20	2355	31
19170	공지	규칙 v2022.02.16 [8]	*0xrgb*	22.02.06	6787	36
1	공지	와 PS! [24]	*0xrgb*	18.05.28	21821	30
45210	일반	ps 뒤늦게 입문했는데 그냥 많이 풀면 되나요 [2]	똑단발	10:37	15	0
45209	일반	어우 실골 구간 들어가니까 정답률 씹창나네 [1]	개허접임	09:34	48	0
45208	일반	c++ 관련 블로그 신고함. [7]	ㅇㅇ(125.209)	06:38	231	1
45207	일반	다음생엔 savior of cross로 [1]	개드립퍼	01:54	172	2
45206	일반	오렌지는 플5랜디 시간안에 해야할정도가 되야는건가 [9]	개드립퍼	01:52	235	0
45205	일반	갑자기 솔브닥 안되는 것 같음 [1]	ㅇㅇ(211.234)	00:13	202	0
45204	일반	쌩뉴비) c언어 공부중인데 질문있음.. [8]	ㅇㅇ(118.130)	06.02	180	0
45203	일반	모스 알고리즘이 은근 꿀단지네 [1]	ㅇㅇ(14.51)	06.02	175	0
45202	일반	영재고 전교 1등은 얼마나 천재임? [4]	ㅇㅇ(223.38)	06.02	299	3
45201	일반	구체수학 이라는 책 아는사람???? [3]	ㅇㅇ(110.14)	06.02	167	0
45200	일기	나도 PS 일찍 시작 안한거 후회되더라	ㅇㅇ(61.43)	06.02	162	2
45199	일반	스포 [2]	ㅇㅇ(61.76)	06.02	225	0
45198	일반	boj 랜디 저만 작동 안되나요? [1]	ㅇㅇ(182.231)	06.02	130	0
45197	일반	나도 고딩때 포기했던거 너무 후회된다 [7]	ㅇㅇ(61.102)	06.02	231	1
45196	일반	와 백준 플레문제 아다 깼다	ㅇㅇ	06.02	155	5
45195	일반	행렬 곱셈 순서 드디어 이해했더 [5]	ㅇㅇ(182.215)	06.02	247	2
45194	일반	요즘 고딩시절 후회됨 [7]	ㅇㅇ(223.62)	06.02	254	0
45193	일반	기분탓인가 [3]	ㅇㅇ(182.231)	06.02	141	1
45192	일반	코포 시간대만 새벽까지가 아니여도 했을텐데 [2]	ㅇㅇ(220.93)	06.02	131	1
45191	질문	ctf는 컴과 고인물 전용인건가요? [5]	ㅇㅇ(125.130)	06.02	223	0
45190	일반	이거 무에서 유를 생각해내는거 가능함? [3]	ㅇㅇ(116.37)	06.02	251	0
45189	일반	탑100 똥색 없애기 얼마 안 남았다	연두집사	06.02	178	2
45188	일반	내 풀이가 왜 틀렸는지를 모를 때 화가남 [3]	ㅇㅇ(182.215)	06.02	202	0
45187	일반	현타온다 [3]	ㅇㅇ(14.52)	06.02	172	0
45186	일반	타과 입장에서 컴공은 경외감들어 [1]	ㅇㅇ(125.130)	06.02	289	0
45185	일반	쓸거없어서 코포점수 쓰고 붙음 [2]	ㅇㅇ(39.7)	06.02	297	0
45184	일반	방학때 알고리즘 공부좀 병행하려하는데 [2]	ㅇㅇ(220.89)	06.02	185	0
45183	일반	혹시 게임 찾아주실 분 계신가요? [8]	…(121.176)	06.02	384	25
45182	일반	근데 신입채용은 어필하기 나름임	ㅇㅇ(218.48)	06.02	228	0
45181	일반	이력서에 쓸게 학력이랑 자격증 밖에 없네 [13]	ㅇㅇ(211.234)	06.02	403	0
45179	질문	런타임에러 InvalidNextSize [2]	ㅇㅇ(223.62)	06.02	118	0
45178	일반	그래서 그냥 안나대기로했음.. [5]	ㅇㅇ(125.137)	06.02	286	1
45177	일반	막말로 날먹 문제 복붙해서 내면 플다 그냥 찍잖아 [1]	ㅇㅇ(106.101)	06.02	204	1
45176	일반	컴공이 유독 이상한 애들이 많은듯 [5]	ㅇㅇ(125.137)	06.02	380	7
45175	일반	태그의 힘을 갈수록 알게됨 [3]	ㅇㅇ(1.243)	06.02	206	0
45174	일반	자력솔 기준 [2]	옥토끼	06.02	307	9
45173	일반	프로그래머스 존나 어렵네	ㅇㅇ(39.7)	06.02	87	0
45172	일반	오렌진데 골랜디 막혔다 [5]	ㅇㅇ(182.231)	06.02	216	0
45171	일반	python vs pypy3 절망편 [4]	ㅇㅇ(121.190)	06.02	317	21
45170	일반	나 다 배껴서 백준 다이아 4찍엇는데 이거 이력서에 써도되냐? [2]	ㅇㅇ(106.101)	06.02	277	1
45169	일반	python vs pypy3 비교 [4]	ㅇㅇ(123.214)	06.02	289	0
45167	일반	게임이론 유형 질문	ㅇㅇ(220.76)	06.02	110	0
45166	일반	실력 오른걸 처음 체감해봄	ㅇㅇ(223.38)	06.02	259	9
45165	일반	ABC E xudyh's sieve처럼 하면 터지네	ㅇㅇ(119.194)	06.01	142	0
45164	일반	나는 똥멍청이다 [1]	ㅇㅇ(180.70)	06.01	138	0
45163	일반	ARC 언제쯤부터 시작하는 게 좋음? [5]	ㅇㅇ(61.43)	06.01	171	0
45161	일반	교내 프로그래밍 대회 1등이라도 하고 써라 [1]	ㅇㅇ	06.01	341	0
45160	일반	백준 루비정도면 이력서에 쓸만하지않냐?? [8]	ㅇㅇ(118.218)	06.01	466	3
45158	일반	백준 플레 한국에 몇천명밖에없는데 이력서에 쓰면안됨? [14]	ㅇㅇ(211.36)	06.01	501	0
45157	일반	자력솔 기준 [15]	ㅇㅇ(14.4)	06.01	417	10