[BOJ] 1525 / 퍼즐 / Python 파이썬

[BOJ] 1525 / 퍼즐 / Python 파이썬

[BOJ] 1525 / 퍼즐 / Python 파이썬

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

1525번: 퍼즐

 

풀이

Data 의 저장형태를 고려해야 하는 BFS 완전탐색 문제이다.

 

3 X 3 퍼즐이 주어지는데, 익숙하게 List 로 진행한다면 Deep Copy 문제와 함께 시간초과를 만나게 된다.

 

3 X 3 퍼즐의 좌표를 1열로 바꿔주고, List 가 아닌 String 으로 Data 를 저장하여 해결 하였다.

문제를 풀면서 자연스럽게 발생하는 문제를 예측하고, 해결하기 위한 설계로 어려움 없이 해결하여 풀이과정이 매우 만족스러웠다.

(무려 골드2 문제였다!)

 

from collections import deque

insNum = ""
for _ in range(3):
    insNum += "".join(input().split())

idx = insNum.index("0")

match = "123456780"


def change(idx, nums):
    U = D = R = L = ""
    if idx > 2:
        tmp = list(nums)
        tmp[idx - 3], tmp[idx] = tmp[idx], tmp[idx - 3]
        U = "".join(tmp)

    if idx < 6:
        tmp = list(nums)
        tmp[idx + 3], tmp[idx] = tmp[idx], tmp[idx + 3]
        D = "".join(tmp)

    if idx < 8 and idx % 3 < 2:
        tmp = list(nums)
        tmp[idx + 1], tmp[idx] = tmp[idx], tmp[idx + 1]
        R = "".join(tmp)

    if idx > 0 and idx % 3 > 0:
        tmp = list(nums)
        tmp[idx - 1], tmp[idx] = tmp[idx], tmp[idx - 1]
        L = "".join(tmp)

    return U, D, R, L

queue = deque()
queue.append([idx, insNum, 0])
res = -1
visited = set()

while queue:
    idx, nums, cnt = queue.popleft()

    if nums == match:
        res = cnt
        break

    U, D, R, L = change(idx, nums)
    if U and U not in visited:
        queue.append([idx-3, U, cnt+1])
        visited.add(U)

    if D and D not in visited:
        queue.append([idx+3, D, cnt+1])
        visited.add(D)

    if R and R not in visited:
        queue.append([idx+1, R, cnt+1])
        visited.add(R)

    if L and L not in visited:
        queue.append([idx-1, L, cnt+1])
        visited.add(L)

print(res)