[백준알고리즘] 1525번: 퍼즐 -Python

[백준알고리즘] 1525번: 퍼즐 -Python

https://www.acmicpc.net/problem/1525

1525번: 퍼즐

보다시피 시간제한과 메모리 제한이 심한 문제이다. 처음 보고는 문제를 어떻게 풀어야 하나 캄캄했다...

 

일반적인 BFS방식으로는 불가능할 것 같고, 방문 유무를 체크해줌으로써 중복을 제거해야 하는데, 3x3크기의 배열을 어떻게 전체적인 모양을 가지고 방문 여부를 표시할 수 있을까 고민했다.

 

결국에 질문 게시판들을 보고 깨우치게 되었다. 조금만 더 쫄지않고 생각해봤으면 나왔을 수도 있지 않았을까 하는 아쉬움이 있다.

 

 

질문 게시판에 의하면 비트마스크로도 풀 수도 있고, 해싱으로도 풀 수 있다고 했다. 해싱으로 3x3크기의 배열의 형태를 압축시킬 수 있다고 생각했고, 바로 딕셔너리를 사용했다. 비트마스크로 푸는 법은 모르겠다.....

방문 여부를 list로 하는 것이 아니라 딕셔너리에 등록을 함으로써 점검할 수 있는 것이다.

 

그럼 여기서 딕셔너리의 키를 어떻게 할지가 문제가 되는데, 여기서는 3x3행렬의 모든 좌표를 일렬로 나열한 것을 key로 하고, 거기까지 움직인 수를 value로 갖도록 했다.

 

예를 들어서 다음과 같이 key를 정했다.

1 0 3

4 2 5

7 8 6

→ key : "103425786"

 

이런 식으로 딕셔너리를 통해 방문 여부를 점검하면 3x3크기의 배열의 형태를 메모리 제한 오류가 발생하지 않고도 다룰 수 있게 됐다.

 

 

이렇게까지 하니 간단하게 구현할 수 있었다. 상하좌우로 이동할 수 있고 아직 점검하지 않은 형태의 모습 (딕셔너리의 키)라면 큐에 넣도록 했다.

 

 

TL, ML 모두 신경은 쓰면서 코딩을 하되 너무 쫄면 안 되겠다..

import sys
from collections import deque
 
def solve():
    queue = deque([table])
    visit = {table:0}
    
    while queue:
        q = queue.popleft()
        step = visit.get(q)
        zero = q.index('0')
 
        if q == '123456780':
            return step
 
        i = zero//3
        j = zero - 3*(zero//3)
 
        # print(q, step)
        step += 1
        ql = list(q)
        if i > 0: # move UP
            ql[zero], ql[zero-3] = ql[zero-3], ql[zero]
            qs = ''.join(ql)
            if not visit.get(qs):
                visit[qs] = step
                queue.append(qs)
            ql[zero], ql[zero-3] = ql[zero-3], ql[zero]
 
        if i < 2: # move DOWN
            ql[zero], ql[zero+3] = ql[zero+3], ql[zero]
            qs = ''.join(ql)
            if not visit.get(qs):
                visit[qs] = step
                queue.append(qs)
            ql[zero], ql[zero+3] = ql[zero+3], ql[zero]
        
        if j > 0: # move LEFT
            ql[zero], ql[zero-1] = ql[zero-1], ql[zero]
            qs = ''.join(ql)
            if not visit.get(qs):
                visit[qs] = step
                queue.append(qs)
            ql[zero], ql[zero-1] = ql[zero-1], ql[zero]
            
        if j < 2: # move RIGHT
            ql[zero], ql[zero+1] = ql[zero+1], ql[zero]
            qs = ''.join(ql)
            if not visit.get(qs):
                visit[qs] = step
                queue.append(qs)
            ql[zero], ql[zero+1] = ql[zero+1], ql[zero]
 
    return -1
 
table = ''
for i in range(3):
    table += ''.join(sys.stdin.readline().split())\
 
print(solve())

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다