1525. 퍼즐

문제 링크

1525. 퍼즐

문제 코드

from collections import deque
import copy

answer = "123456780"
graph = ""

for i in range(3):
    num_list = list(map(int,input().split()))
    for j in range(3):
        graph+=str(num_list[j])

visited_graph_list =set(graph)

que = deque()

que.append((graph,0))

print_idx = 0
result = -1
while len(que)>0:
    tmp_graph,count = que.popleft()

    if tmp_graph == answer:
        result = count
        break

    blank = tmp_graph.find('0')

    dp = [-1,1,-3,3]

    for i in range(4):
        if (i == 0 and blank in [3,6]) or (i ==1 and blank in [2,5]):
            continue

        next_pos = blank+dp[i]

        if 0<=next_pos<9:
            new_graph=""
            for j in range(9):
                if j == blank:
                    new_graph+=tmp_graph[next_pos]
                elif j == next_pos:
                    new_graph+=tmp_graph[blank]
                else:
                    new_graph+=tmp_graph[j]
            #print(new_graph)

            if new_graph not in visited_graph_list:
                que.append((new_graph,count+1))
                visited_graph_list.add(new_graph)
print(result)

문제 풀이

• 처음에는 3*3 이차원배열로 풀려고 했다.
• visited 비교하는데에 너무나 많은 시간이 걸림
• 문자열로 바꿔서 수행하고, 3 <->4 , 6<->7 swap 안하도록 조건 걸어줌
• que에 리스트 형태로 넣는것보다 set으로 넣는게 훨씬 시간 단축 해줌