카드 짝 맞추기

import itertools from math import inf from copy import deepcopy from collections import deque, defaultdict def solution(board, r, c): initr, initc = r, c R, C = len(board), len(board[0]) # 카드 종류가 6개밖에 안 됩니다. # 탐색 순서의 모든 경우의 수는 최대 2^6 x 6! = 46080 가지밖에 없습니다. # 브루트포스로 해결 가능해보입니다. # 1부터 maxval 까지 종류의 카드가 있습니다. maxval = max(board[r][c] for r in range(R) for c in range(C)) # 문제 해결을 위한 함수들을 작성해봅시다. # (r1, c1)에서 (r2, c2)로 최소 조작으로 이동할 때 조작 횟수 # BFS로 계산하면 됩니다. def move(r1, c1, r2, c2, B): # BFS가 필요 없는 자명한 위치 관계들은 따로 처리해주는 식으로 # 시간 최적화를 조금 해줍니다. 이래야 10초 이내로 빡빡하게 통과... if r1 == r2: cmin, cmax = min(c1, c2), max(c1, c2) if cmax - cmin == 1: return 1 elif cmax - cmin == 2 and B[r1][cmin+1] == 0: return 1 elif cmax - cmin == 3 and B[r1][cmin+1] == 0 and B[r1][cmin+2] == 0: return 1 if c1 == c2: rmin, rmax = min(r1, r2), max(r1, r2) if rmax - rmin == 1: return 1 elif rmax - rmin == 2 and B[rmin+1][c1] == 0: return 1 elif rmax - rmin == 3 and B[rmin+1][c1] == 0 and B[rmin+2][c1] == 0: return 1 q, vis = deque(), set() q.append( (0, r1, c1) ) vis.add( (r1, c1) ) while q: d, r, c = q.popleft() if r == r2 and c == c2: return d # 상하좌우 1칸씩 for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]: if 0 <= r+dr < R and 0 <= c+dc < C: if (r+dr, c+dc) not in vis: q.append( (d+1, r+dr, c+dc) ) vis.add( (r+dr, c+dc) ) # 1. 위쪽으로 이동 if dr == -1 and dc == 0 and B[r+dr][c+dc] == 0: nr, nc = r+dr, c+dc while nr > 0 and B[nr][nc] == 0: nr -= 1 if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in vis: q.append( (d+1, nr, nc) ) vis.add( (nr, nc) ) # 2. 오른쪽으로 이동 elif dr == 0 and dc == 1 and B[r+dr][c+dc] == 0: nr, nc = r+dr, c+dc while nc < C-1 and B[nr][nc] == 0: nc += 1 if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in vis: q.append( (d+1, nr, nc) ) vis.add( (nr, nc) ) # 3. 왼쪽으로 이동 elif dr == 0 and dc == -1 and B[r+dr][c+dc] == 0: nr, nc = r+dr, c+dc while nc > 0 and B[nr][nc] == 0: nc -= 1 if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in vis: q.append( (d+1, nr, nc) ) vis.add( (nr, nc) ) # 4. 아래쪽으로 이동 elif dr == 1 and dc == 0 and B[r+dr][c+dc] == 0: nr, nc = r+dr, c+dc while nr < R-1 and B[nr][nc] == 0: nr += 1 if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in vis: q.append( (d+1, nr, nc) ) vis.add( (nr, nc) ) # 모든 경우의 수를 탐색해봅니다. # order: 카드 종류를 탐색하는 순서 # cards[카드 종류] : 카드 위치들 cards = defaultdict(list) for r in range(R): for c in range(C): if board[r][c] != 0: cards[board[r][c]].append((r, c)) mn = inf for order in itertools.permutations(range(1, maxval + 1)): # mask: 먼저 탐색된 카드를 먼저 볼 것인지 (0), 아닌지 (1) for mask in itertools.product([0, 1], repeat=maxval): # 이하가 탐색의 한 가지 경우의 수입니다. skip = False B = [[row[c] for c in range(C)] for row in board] nmove, path = 0, [] # 각각의 카드를 찾아서 위치를 기록해둡니다. for val, reverse in zip(order, mask): cardpos = cards[val][::-1] if reverse else cards[val] path.extend(cardpos) # 이제 path 순서대로 따라가면서 이동하면 됩니다. currr, currc = initr, initc nmove = 0 for i, (r, c) in enumerate(path, 1): nmove += move(currr, currc, r, c, B) # (최적화) 지금까지의 최솟값보다 크면 탐색을 멈춥니다. if nmove >= mn: skip = True break currr, currc = r, c B[r][c] = 0 if skip: continue if nmove < mn: mn = nmove return mn + maxval * 2