[백준 | Python] #2549 - 루빅의 사각형 (IDA* 알고리즘)

2549번: 루빅의 사각형

문제

4*4의 격자판의 각 타일에 1부터 16까지의 숫자가 적혀있다. 행을 밀거나 열을 밀어서 격자판의 숫자를 순서대로 정렬할 때 그 최소 이동 수와 이동 경로를 출력하라.

아이디어

15퍼즐이 생각나는 문제이다. 15퍼즐은 IDA* 알고리즘을 이용해 그나마 빠른 속도로 해결할 수 있다.

또한 15퍼즐은 각 이동의 소요 비용이 1이므로 IDA* 알고리즘에서 우선순위 큐를 사용할 필요가 없다.

이 문제도 IDA* 알고리즘을 적용할 수 있을 것 같아 보인다.

관건은 휴리스틱 함수를 어떻게 정의하느냐인데 그 아이디어는 다음과 같다.

1. 하나의 움직임에 4개의 타일이 움직인다.
2. 따라서 위치가 틀린 것이 n개 있다면 그 격자판은 적어도 n/4의 움직임이 필요하다.

결론

• 모든 타일에 대해 행과 열이 적절한 위치인지 검사한다. 적절하지 않다면 distance에 1을 더한다.
• distance를 4로 나눈 몫이 그 격자판의 최적 이동 수의 휴리스틱 함수로 기능한다.

구현

전형적인 IDA* 알고리즘이다.

while loop에서 max_move에 대한 iterative deepening을 담당하고

heuristic function은 calc_distance(board) // 4이다.

격자판이 정렬되었는지는 distance == 0임을 통해 판단할 수 있다.

각 행과 각 열에 대해 1, 2, 3칸 미는 움직임을 모두 재귀로 구현한다.

코드

# 휴리스틱 함수
def calc_distance(board):
    dis = 0
    for i in range(4):
        for j in range(4):
            dis += (board[i][j] // 4 != i) + (board[i][j] % 4 != j)
    return dis

# A* 재귀
def solve(board, left_move_count, route):
    distance = calc_distance(board)

    if distance == 0: return route
    if left_move_count < distance // 4: return None

    for row in range(4):
        for moves in range(1,4):
            board[row][0],board[row][1],board[row][2],board[row][3] = board[row][3],board[row][0],board[row][1],board[row][2]
            sol = solve(board, left_move_count-1, route+[(1, row+1, moves)])
            if sol: return sol
        board[row][0],board[row][1],board[row][2],board[row][3] = board[row][3],board[row][0],board[row][1],board[row][2]

    for col in range(4):
        for moves in range(1,4):
            board[0][col],board[1][col],board[2][col],board[3][col] = board[3][col],board[0][col],board[1][col],board[2][col]
            sol = solve(board, left_move_count-1, route+[(2, col+1, moves)])
            if sol: return sol
        board[0][col],board[1][col],board[2][col],board[3][col] = board[3][col],board[0][col],board[1][col],board[2][col]

    return None


board = [list(map(lambda x: int(x)-1, input().split())) for _ in range(4)]

# iterative deepening
max_move = 0
while 1:
    sol = solve(board, max_move, [])

    if sol:
        print(max_move)
        for route in sol:
            print(*route)
        break
    max_move += 1

 

후기

15퍼즐 처돌이라 플레2 치고 되게 금방 해결했다.

양방향 BFS로 해결하는 방법도 있는 것 같다.

이 부분은 잘 몰라서 공부해야할 것 같다.

C++은 heuristic 없이 iterative deepening DFS로 해결이 가능한 것 같다.