[BOJ] 1525 - 퍼즐 (Python)

 

 

아이디어

 

BFS로 정리된 상태에서부터 초기 상태가 될 때까지 탐색해 나간다(반대의 경우도 가능).

 

 

풀이

 

퍼즐의 상태를 편리하게 나타내기 위해 문자열로 처리하고, 자리 이동이 가능한 인덱스들을 리스트 move에 저장한다.

초기 상태를 문자열로 result에 저장하고, 함수 find를 호출해 반환값을 출력하도록 한다.

 

함수 find에서는 덱 queue에 정리된 상태, 0의 위치, 이동 횟수를 튜플로 삽입하고 BFS한다.

초기 상태와 정리된 상태가 같은 경우 곧바로 0을 반환하고, queue가 빌 때까지 초기 상태가 되지 못하면 -1을 반환한다.

현재 상태 now, 0의 위치 idx, 현재 이동 횟수 cnt를 차례로 queue에서 꺼낸 다음,

for문에서 이동 후의 상태 문자열 s를 만들고 s가 초기 상태 result가 되면 현재 이동 횟수를 반환한다.

이동 후의 상태 문자열 s는 세트 visited에 추가하여 이후 방문 여부를 확인하도록 한다.

 

문자열 s는 슬라이싱을 통해 현재 상태에서 0이 이동하고자 하는 위치 i의 숫자를 0으로 바꿔 저장하고,

0으로 바뀐 위치 i의 원래 숫자를 원래 0의 위치 idx에 넣어 저장하여 퍼즐의 상태를 바꾼다.

 

import sys
from collections import deque

input = sys.stdin.readline

move = [(1, 3), (0, 2, 4), (1, 5), (0, 4, 6), (1, 3, 5, 7), (2, 4, 8), (3, 7), (4, 6, 8), (5, 7)]

def find():
    original = '123456780'
    if original == result:
        return 0
    queue = deque([(original, 8, 1)])
    visited = set()
    while queue:
        now, idx, cnt = queue.popleft()
        for i in move[idx]:
            s = now[:i]+now[idx]+now[i+1:]
            s = s[:idx]+now[i]+s[idx+1:]
            if s not in visited:
                if s == result:
                    return cnt
                queue.append((s, i, cnt+1))
                visited.add(s)
    return -1

result = ''
for _ in range(3):
    for n in input().split():
        result += n
print(find())

 

 

덱을 사용하지 않고 pop(0)으로 BFS하는 경우, 약 2.9배 느렸다.

# 더 느린 코드
queue = [(original, 8, 1)]
visited = set()
while queue:
    now, idx, cnt = queue.pop(0)

 

현재 상태와 초기 상태를 큐 삽입 전에 확인하지 않고 그 이후에 확인하는 코드는 메모리가 더 많이 사용되고 더 느렸다.

# 메모리가 더 많이 사용되고 더 느린 코드
while queue:
    now, idx, cnt = queue.popleft()
    if now == result:
        return cnt
    for i in move[idx]:
        s = now[:i]+now[idx]+now[i+1:]
        s = s[:idx]+now[i]+s[idx+1:]
        if s not in visited:
            queue.append((s, i, cnt+1))
            visited.add(s)