[백준 1525 : PYTHON] 퍼즐

문제 풀기 : 1525번

1525번: 퍼즐

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 최소 이동 횟수 구한다.

문제풀이

모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다.

빈칸인 부분의 상, 하, 좌, 우와 빈칸을 바꿔가며 탐색한다.

이 때, 위의 표를 만족하는 배열을 찾는 방법으로 표에 있는 숫자를 문자열로 바꾸는 방식을 사용한다.

• 빈칸 숫자 0은 9로 바꾼 후 진행한다. (sort가 용이하도록)

문자열을 다룰 때 유의할 조건들은

1. 이동된 상태를 저장하는 큐를 사용해서 찾는 문자열과 비교한다.

2. 각 단계의 이동한 회수를 저장하기 위해 딕셔너리를 사용한다.

3. 현재 빈칸이 위치한 곳의 행과 열을 구할 땐 문자열의 위치(index)로 찾는다.

   

코드 TIP

• 문자열인 상태에서 요소들의 변경은 불가하기 때문에 list 형태로 바꾼 후 요소를 변경해주어야 한다.

• 딕셔너리(dict())

  예) [{'123456789', 0}]

전체코드

import sys
from collections import deque

# 상, 하, 좌, 우
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs():

    while q:
        now = q.popleft()

        # 만족하는 퍼즐일 경우 이동횟수 리턴
        if now == "123456789":
            return cntDict[now]

        # 현재 빈칸 위치 (행, 열) 
        pos = now.find("9")
        x = pos // 3
        y = pos % 3

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 3 and 0 <= ny < 3:
                # 이동할 위치
                nPos = nx * 3 + ny
                # 이동된 상태 설정
                nextNum = list(now)
                nextNum[nPos], nextNum[pos] = nextNum[pos], nextNum[nPos]
                nextNum = "".join(nextNum)

                if not cntDict.get(nextNum):
                    # 이동된 상태 저장, 이동횟수 + 1
                    q.append(nextNum)
                    cntDict[nextNum] = cntDict[now] + 1


# 초기 퍼즐 상태
start = ""
for _ in range(3):
    # 입력 -> 123456780 형태로 변환
    temp = sys.stdin.readline().strip()
    temp = temp.replace(" ", "")
    start += temp

start = start.replace("0", "9")

# 이동된 상태 저장
q = deque()
q.append(start)

# 이동된 상태, 이동횟수 저장
cntDict = dict()
cntDict[start] = 0

# 이동이 불가하면 "-1"을 출력
result = bfs()
print(result if result != None else "-1" )