[BOJ] 퍼즐 (1525, G2)

 

아이디어는 BFS를 활용한 빡구현. 처음에 퍼즐판에 나올 수 있는 경우를 확장하여 9!로 visited를 생성하고,

최단 턴 수 이므로, 한 번 나온 배열은 다시 나오지 않게 처리한다.

이 때, 퍼즐의 이동을 2차원 배열이 아닌 문자열로 처리.

더불어, 명백하게 풀이가 불가능한 케이스로 예외 처리를 하여 조금 속도 이득을 보려고 했는데... 비효율 풀이 같다...

import sys
from collections import deque
input = sys.stdin.readline
def dfs(level, ans):
    if level == 9:
        puzzle_dict[ans] = False
        return
    else:
        for i in range(0, 9):
            if not visited[i]:
                ans += str(i)
                visited[i] = True
                dfs(level + 1, ans)
                ans = ans[:-1]
                visited[i] = False

def puzzle_to_str(puzz):
    ans = ''
    for i in range(3):
        for j in range(3):
            ans += str(puzz[i][j])
    return str(ans)

# step 1 / vistied 저장할 dict를 만든다.
puzzle_dict = {}
visited = [False] * 9
dfs(0, '')

start_pos = []
for _ in range(3):
    start_pos.append(list(map(int, input().split())))
goal_pos = '123456780'

# step 2 / 하나씩 움직여서 판단한다.
q = deque()
start_str = puzzle_to_str(start_pos)
q.append([0, start_str])
answer = -1
while q:
    # 2-1 정답 확인
    cur_turn, cur_puzz = q.popleft()
    if cur_puzz == goal_pos:
        answer = cur_turn
        break
    # 하나씩 바뀐거는 불가능이라. 그거를 fail case로 넣어둬서 실패 판단 빠르게
    elif cur_puzz in ['123456870', '213456780', '132456780', '124356780', '123546780', '123465780', '123457680',
                          '423156780', '123756480', '153426780', '123486750', '126453780', '173456280', '128456730']:
        answer = -1
        break
    # 2-2 방문 처리 후 이동 파트
    puzzle_dict[cur_puzz] = True
    zero_pos = cur_puzz.index('0')
    # 아래와 변경 가능
    if zero_pos in [0, 1, 2, 3, 4, 5]:
        new_answer = ''
        for i in range(9):
            if i == zero_pos:
                new_answer += cur_puzz[i + 3]
            elif i == zero_pos + 3:
                new_answer += cur_puzz[i - 3]
            else:
                new_answer += cur_puzz[i]
        if not puzzle_dict[new_answer]:
            puzzle_dict[new_answer] = True
            q.append([cur_turn + 1, new_answer])
    # 위와 변경 가능
    if zero_pos in [3, 4, 5, 6, 7, 8]:
        new_answer = ''
        for i in range(9):
            if i == zero_pos:
                new_answer += cur_puzz[i - 3]
            elif i == zero_pos - 3:
                new_answer += cur_puzz[i + 3]
            else:
                new_answer += cur_puzz[i]
        if not puzzle_dict[new_answer]:
            puzzle_dict[new_answer] = True
            q.append([cur_turn + 1, new_answer])
    # 왼쪽과 변경 가능
    if zero_pos in [1, 2, 4, 5, 7, 8]:
        new_answer = ''
        for i in range(9):
            if i == zero_pos:
                new_answer += cur_puzz[i - 1]
            elif i == zero_pos - 1:
                new_answer += cur_puzz[i + 1]
            else:
                new_answer += cur_puzz[i]
        if not puzzle_dict[new_answer]:
            puzzle_dict[new_answer] = True
            q.append([cur_turn + 1, new_answer])
    # 오른쪽과 변경 가능
    if zero_pos in [0, 1, 3, 4, 6, 7]:
        new_answer = ''
        for i in range(9):
            if i == zero_pos:
                new_answer += cur_puzz[i + 1]
            elif i == zero_pos + 1:
                new_answer += cur_puzz[i - 1]
            else:
                new_answer += cur_puzz[i]
        if not puzzle_dict[new_answer]:
            puzzle_dict[new_answer] = True
            q.append([cur_turn + 1, new_answer])
print(answer)