[파이썬] 백준 1525 : 퍼즐 (골드2)

[파이썬] 백준 1525 : 퍼즐 (골드2)

 

---

문제

---

풀이

0. 방향성 생각

9!의 경우의 수를 탐색하는 것과 같다.

2차원 배열을 문자열로 바꾸어서 집합 visit에 넣은 후 탐색한다.

1. 입력

from collections import deque

arr = []
for _ in range(3):
    arr.extend(input().split())
arr = ''.join(arr)

리스트로 받아준 후 문자열로 변환한다.

2. 방향 정의

moves = {0:(1,3), 2:(1,5), 6:(3,7), 8:(5,7),
         1:(0,2,4), 3:(0,4,6), 5:(2,4,8), 7:(4,6,8),
         4: (1,3,5,7)}

2차원 배열에서 왼쪽 위부터 0,1,2,...7,8 이라 하면, 인접한 위치로 갈 수 있다.

0의 위치가 주어지면 다음 이동가능한 0의 인덱스 목록 정의.

 

3. 출력

find = False
while q:
    x,count = q.popleft()
    if x == answer:
        find = True
        break
    else:
        x = list(x)
        idx = x.index('0')
        for nidx in moves[idx]:
            x_temp = list(x)
            x_temp[idx],x_temp[nidx] = x_temp[nidx],x_temp[idx]
            nx = ''.join(x_temp)
            if nx not in visit:
                q.append((nx,count+1))
                visit.add(nx)

if find: print(count)
else: print(-1)

x의 0 위치를 찾아주고, 다음 이동 방향을 탐색한다.

x를 바꾸면 꼬일 수 있으니 list(x)로 새로운 x_temp 정의한다.

서로 위치 바꿔주고 문자열로 변환

이 변환된 문자열이 방문 안돼있으면 큐에 추가.

---

전체코드

from collections import deque

arr = []
for _ in range(3):
    arr.extend(input().split())
arr = ''.join(arr)

answer = '123456780'
visit = set([arr])
q = deque([(arr, 0)])

moves = {0:(1,3), 2:(1,5), 6:(3,7), 8:(5,7),
         1:(0,2,4), 3:(0,4,6), 5:(2,4,8), 7:(4,6,8),
         4: (1,3,5,7)}

find = False
while q:
    x, count = q.popleft()
    if x == answer:
        find = True
        break
    else:
        x = list(x)
        idx = x.index('0')
        for nidx in moves[idx]:
            x_temp = list(x)
            x_temp[idx],x_temp[nidx] = x_temp[nidx],x_temp[idx]
            nx = ''.join(x_temp)
            if nx not in visit:
                q.append((nx,count+1))
                visit.add(nx)

if find: print(count)
else: print(-1)