백준 1525 퍼즐 Python 3

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

1525번: 퍼즐

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1525.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

from collections import deque, defaultdict
import sys, copy
def puzzle_to_str(puzzle):
    str_q = ""
    for row in puzzle:
        str_q += "".join(map(str, row))
    return str_q
def play(x, y):
    visit = defaultdict(int)
    q = deque([[copy.deepcopy(puzzle), 0, x, y]])
    visit[puzzle_to_str(puzzle)] = 1

    while q:
        pz, cnt, zx, zy = q.popleft()
        if puzzle_to_str(pz) == "123456780":
            print(cnt)
            return
        for ddx, ddy in zip(dx, dy):
            nzx = zx+ddx
            nzy = zy+ddy
            if 0 <= nzx < 3 and 0 <= nzy < 3:
                pz[zy][zx], pz[nzy][nzx] = pz[nzy][nzx], pz[zy][zx]
                str_pz = puzzle_to_str(pz)
                if visit[str_pz] == 0:
                    visit[str_pz] = 1
                    q.append([copy.deepcopy(pz), cnt+1, nzx, nzy])
                pz[zy][zx], pz[nzy][nzx] = pz[nzy][nzx], pz[zy][zx]

    print(-1)

input = sys.stdin.readline
puzzle = list()
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
for y in range(3):
    puzzle.append(list(map(int, input().split())))
    for x in range(3):
        if puzzle[y][x] == 0:
            zx, zy = x, y
play(zx, zy)

---

풀이 과정

풀이 시간 31분

3x3 퍼즐을 빈 칸과 상하좌우로 인접한 칸을 빈 칸으로 옮겨가며 퍼즐을 아래와 같이 맞추는 문제이다.

BFS로 풀기 위해 변화하는 퍼즐의 상태를 큐에 담아가며 문제를 해결했다.

퍼즐이 3x3 크기이기 때문에 메모리 초과 없이 문제를 해결 할 수 있었다.

from collections import deque, defaultdict
import sys, copy

def puzzle_to_str(puzzle):
    str_q = ""
    for row in puzzle:
        str_q += "".join(map(str, row))
    return str_q
    
def play(x, y):
	#방문처리 - 리스트 타입의 퍼즐을 str로 변환해서 방문처리 한다
    visit = defaultdict(int)
    
    #퍼즐, 이동 횟수, 빈칸의 위치를 큐에 담아가며 탐색한다
    q = deque([[copy.deepcopy(puzzle), 0, x, y]])
    visit[puzzle_to_str(puzzle)] = 1

    while q:
        pz, cnt, zx, zy = q.popleft()
        
        #퍼즐이 맞춰진 경우, 이동 횟수를 출력하고 함수를 종료한다
        if puzzle_to_str(pz) == "123456780":
            print(cnt)
            return
        
       	#빈 칸의 인접한 4방향 탐색
        for ddx, ddy in zip(dx, dy):
            nzx = zx+ddx
            nzy = zy+ddy
            if 0 <= nzx < 3 and 0 <= nzy < 3:
            	#(nzx, nzy) 칸의 숫자와 빈 칸을 바꾼다
                pz[zy][zx], pz[nzy][nzx] = pz[nzy][nzx], pz[zy][zx]
                str_pz = puzzle_to_str(pz)
                
                #이전에 방문처리 되지 않은 퍼즐 상태인 경우, 방문 처리 후 큐에 담아준다
                if visit[str_pz] == 0:
                    visit[str_pz] = 1
                    q.append([copy.deepcopy(pz), cnt+1, nzx, nzy])
                    
                #다시 원래 퍼즐의 상태로 돌린다
                pz[zy][zx], pz[nzy][nzx] = pz[nzy][nzx], pz[zy][zx]

    print(-1)

input = sys.stdin.readline
puzzle = list()
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
for y in range(3):
    puzzle.append(list(map(int, input().split())))
    for x in range(3):
        if puzzle[y][x] == 0:
            zx, zy = x, y
play(zx, zy)

#시간복잡도 = O(V+E), 공간복잡도 = O(n^2)