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으로 넣는게 훨씬 시간 단축 해줌
Author And Source
이 문제에 관하여(1525. 퍼즐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@youngjin_kim2/1525.-퍼즐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)