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

---

1. 정답 코드

from itertools import permutations
from collections import deque, defaultdict
from copy import deepcopy


def solution(board, r, c):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    INF = float('inf')

    def bfs(current_x, current_y, target_x, target_y):
        if current_x == target_x and current_y == target_y:
            return 0
        graph = [[INF] * 4 for _ in range(4)]
        graph[current_x][current_y] = 0
        q = deque([(current_x, current_y)])
        while q:
            x, y = q.popleft()
            for dir in range(4):
                nx = x + dx[dir]
                ny = y + dy[dir]
                if 0 <= nx < 4 and 0 <= ny < 4:
                    if graph[nx][ny] > graph[x][y] + 1:
                        graph[nx][ny] = graph[x][y] + 1
                        q.append((nx, ny))
                    # 한 칸 움직인 위치가 카드라면 ctrl 이동 불가
                    if board_copy[nx][ny] != 0:
                        continue
                    # ctrl 이동
                    ctrl_flag = False
                    for _ in range(2):
                        nx += dx[dir]
                        ny += dy[dir]
                        if 0 <= nx < 4 and 0 <= ny < 4:
                            ctrl_flag = True
                            ctrl_x, ctrl_y = nx, ny
                            if board_copy[nx][ny] != 0:
                                break
                    if ctrl_flag:
                        if graph[ctrl_x][ctrl_y] > graph[x][y] + 1:
                            graph[ctrl_x][ctrl_y] = graph[x][y] + 1
                            q.append((ctrl_x, ctrl_y))
        return graph[target_x][target_y]

    answer = INF
    card_len = 0
    all_order_list = []
    d = defaultdict(list)
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0 and board[i][j] not in all_order_list:
                all_order_list.append(board[i][j])
                card_len += 1
    for card in all_order_list:
        for i in range(4):
            for j in range(4):
                if board[i][j] == card:
                    d[card].append((i, j))
    for order in permutations(all_order_list):
        board_copy = deepcopy(board)
        result = card_len * 2
        start_x = r
        start_y = c
        for idx in order:
            # 시작 (1, 0), order = (1, 3, 2)
            # 1A, 1B 중 커서와 더 가까운 카드를 찾는다.
            a = bfs(start_x, start_y, d[idx][0][0], d[idx][0][1])
            b = bfs(start_x, start_y, d[idx][1][0], d[idx][1][1])
            if a < b:
                # result += 커서가 1A 까지 이동하는 비용
                # result += 1A에서 1B까지 이동하는 비용
                # 커서의 위치는 1B로 초기화
                result += a
                result += bfs(d[idx][0][0], d[idx][0][1], d[idx][1][0], d[idx][1][1])
                start_x, start_y = d[idx][1]
            else:
                result += b
                result += bfs(d[idx][1][0], d[idx][1][1], d[idx][0][0], d[idx][0][1])
                start_x, start_y = d[idx][0]
            board_copy[d[idx][0][0]][d[idx][0][1]] = 0
            board_copy[d[idx][1][0]][d[idx][1][1]] = 0
        answer = min(answer, result)
    return answer

solution([[1, 0, 0, 3], [2, 0, 0, 0], [0, 0, 0, 2], [3, 0, 1, 0]], 1, 0)
# solution([[3, 0, 0, 2], [0, 0, 1, 0], [0, 1, 0, 0], [2, 0, 0, 3]], 0, 1)

---

2. 후기

카카오 문제를 풀면서 느낀 점은 순열 또는 조합 라이브러리를 적극적으로 활용해야 한다는 것이
다. 또한 직감으로 최적 알고리즘을 찾기보다는 완전 탐색과 백트래킹을 통한 접근을 요구하는 문제가 생각보다 많았다. 물론 이 문제는 최적 알고리즘이 존재했다.

코드 설명

문제에 대한 전체적인 이해는 카카오 공식 해설 을 먼저 읽어보자.

이 문제 또한 주어질 수 있는 카드의 종류는 최대 6개 밖에 안되기 때문에 순열을 사용해도 많아봐야 720개의 경우의 수밖에 나오지 않기 때문에 순열 라이브러리를 사용해야 한다.

BFS로 최단거리를 탐색하는 과정은 크게 어렵지 않다. 나머지 부분은 주석을 보면 쉽게 이해할 수 있을 것이다. 다시 요약하자면 아래와 같다.

1. 동일한 숫자를 가진 두 카드(1A, 1B) 중 BFS를 통해 현재 커서와 더 가까운 카드를 찾는다.

2. 만약 1A가 현재 커서와 더 가깝다면 1A로 이동한 후 1A에서 1B까지 이동하는 최단거리를 BFS를 통해 한번 더 계산한다.

3. 마지막으로 현재 커서의 위치를 1B로 초기화시킨다.

이 문제의 최적 알고리즘은 어떤 숫자가 적힌 카드를 방문할 때, 현재 커서와 더 가까운 카드를 우선 방문해야 한다는 것이다.

시간 초과 원인

(1A, 1B), (2A, 2B), (3A, 3B) 6개로 나눠서 모든 경우의 수를 구해서 시간초과 발생

1A을 방문할 경우 다음 방문은 무조건 1B 이라는 생각을 한다면 1 2 3 의 순열만 필요하면 된다는 것을 알 수 있다.