https://programmers.co.kr/learn/courses/30/lessons/72415
그리드를 포함한 완전 탐색으로 코드를 구현했다.
결과적으로 코드는 효율성 포함해서 잘 돌아간다. 그러나 greed로 구현하는 방식에 반례가 존재하였다.
a 카드가 a1 a2 이렇게 탐색하는게 a2 a1 로 탐색하는 것 보다 순간적으로는 작다고 해도 그 다음 b라는 카드를 탐색할 때, 시작지점이 a2, a1으로 나뉘어진다. 그러나 a1 a2 b2 b1 의 값이 a2 a1 b2 b1 보다 큰 경우가 존재한다.
결국 앞의 결과가 뒤의 계산에도 영향을 미칠 수 있다는 뜻이다.
from queue import deque
from collections import defaultdict
from itertools import permutations as p
from copy import deepcopy
import sys
def solution(board, r, c):
answer = sys.maxsize
pair = defaultdict(list)
# 카드(1 ~ 6) 별로 좌표를 전부 확인한다. (순열을 돌리기 위한 작업)
for y in range(4):
for x in range(4):
if board[y][x] != 0:
pair[board[y][x]].append((y, x))
# 위에서 각 카드 별로 묶여진 좌표들을 순열로 섞는다.
for order in p(pair.values()):
s_y, s_x = r, c
board2 = deepcopy(board)
temp = 0
# 카드별로 두 장씩 있는데, 순열에 따라 board 형태가 달라지므로
# 같은 모양의 카드 중 무엇을 먼저 뽑아야하는지도 확인해서 키 입력이 작은 걸 선택한다.
for arr in order:
a = find(board2, s_y, s_x, arr[1][0], arr[1][1]) + find(board2, arr[1][0], arr[1][1], arr[0][0], arr[0][1])
b = find(board2, s_y, s_x, arr[0][0], arr[0][1]) + find(board2, arr[0][0], arr[0][1], arr[1][0], arr[1][1])
if a > b:
s_y, s_x = arr[1][0], arr[1][1]
else:
s_y, s_x = arr[0][0], arr[0][1]
board2[arr[1][0]][arr[1][1]] = 0
board2[arr[0][0]][arr[0][1]] = 0
temp += min(a, b) + 2
answer = min(answer, temp)
return answer
# bfs로 시작(s_y, s_x)과 끝(e_y, e_x)이 주어지면 시작에서 끝까지 가는 최단경로를 찾는다.
def find(board, s_y, s_x, e_y, e_x):
que = deque([(s_y, s_x, 0)])
cand = ((1, 0), (0, -1), (-1, 0), (0, 1))
confirm = {(s_y, s_x)}
while que:
y, x, cnt = que.popleft()
if y == e_y and x == e_x:
return cnt
for dy, dx in cand:
y1, x1 = y, x
if 0 <= y + dy < 4 and 0 <= x + dx < 4 and (y + dy, x + dx) not in confirm:
que.append((y + dy, x + dx, cnt + 1))
confirm.add((y + dy, x + dx))
while 0 <= y1 + dy < 4 and 0 <= x1 + dx < 4:
y1 += dy
x1 += dx
if board[y1][x1] != 0:
break
if (y1, x1) not in confirm:
que.append((y1, x1, cnt + 1))
confirm.add((y1, x1))
모든 경우를 확인하는 순열을 dfs를 통해 직접 구현하였다.
from queue import deque
from collections import defaultdict
from copy import deepcopy
import sys
def solution(board, r, c):
pair = defaultdict(list)
for y in range(4):
for x in range(4):
if board[y][x] != 0:
pair[board[y][x]].append((y, x))
return p(list(pair.keys()), (r, c), board, pair)
def find(board, s, e):
s_y, s_x , e_y, e_x = *s, *e
que = deque([(s_y, s_x, 0)])
cand = ((1, 0), (0, -1), (-1, 0), (0, 1))
confirm = {(s_y, s_x)}
while que:
y, x, cnt = que.popleft()
if y == e_y and x == e_x:
board[y][x] = 0
return cnt
for dy, dx in cand:
y1, x1 = y, x
if 0 <= y + dy < 4 and 0 <= x + dx < 4 and (y + dy, x + dx) not in confirm:
que.append((y + dy, x + dx, cnt + 1))
confirm.add((y + dy, x + dx))
while 0 <= y1 + dy < 4 and 0 <= x1 + dx < 4:
y1 += dy
x1 += dx
if board[y1][x1] != 0:
break
if (y1, x1) not in confirm:
que.append((y1, x1, cnt + 1))
confirm.add((y1, x1))
def p(arr, s, board, pair):
if not arr:
return 0
answer = sys.maxsize
for idx, num in enumerate(arr):
a = find(board, s, pair[num][0]) + find(board, pair[num][0], pair[num][1]) + p(arr[:idx] + arr[idx + 1:], pair[num][1], board, pair)
board[pair[num][0][0]][pair[num][0][1]] = num
board[pair[num][1][0]][pair[num][1][1]] = num
b = find(board, s, pair[num][1]) + find(board, pair[num][1], pair[num][0]) + p(arr[:idx] + arr[idx + 1:], pair[num][0], board, pair)
board[pair[num][0][0]][pair[num][0][1]] = num
board[pair[num][1][0]][pair[num][1][1]] = num
answer = min(min(a, b) + 2, answer)
return answer