[백준] 1525번 : 퍼즐

1525번: 퍼즐

1525번: 퍼즐

🤔 문제분석

너비우선탐색, 집합 자료형을 활용하여 문제를 해결하였습니다. “123456780”을 하나의 문자열로 보고 해당문자열을 방문처리 하여 그다음 방문때 방문하지 않도록 합니다. 0의 위치를 파악하고 해당위치에서 갈 수 있는 곳을 선택하여 너비우선탐색합니다.

Serialize 와 Deserialize 함수를 두었는데, Serialize 함수는 2차원 배열을 문자열로 바꾸어주는 함수이고, Deserialize 함수는 문자열을 다시 배열로 바꾸어주는 함수입니다. 탐색을 할때에는 2차원 배열을 사용하고, 방문처리를 할때에는 문자열을 사용하기 때문입니다.

💻 코드

# <https://www.acmicpc.net/problem/1525>
import sys
from collections import deque
from copy import deepcopy

input = sys.stdin.readline

puzzle = []
for _ in range(3):
    puzzle.append(list(map(int, input().split())))
    
def serialize(puzzle):
    temp = ''
    for i in range(3):
        temp += ''.join(map(str, puzzle[i]))
    
    return temp

def deserialize(string):
    temp = [[0 for _ in range(3)] for _ in range(3)]
    for i in range(3):
        for j in range(3):
            temp[i][j] = string[i*3+j]
            
    return temp

def find_zero(puzzle):
    for i in range(3):
        for j in range(3):
            if puzzle[i][j] == '0':
                return i, j

def is_made(puzzle):
    return puzzle == '123456780'
    

def solove(p):
    is_not_found = True
    visited = set()
    start = serialize(p)
    visited.add(start)
    queue = deque([(start, 0)])
    while queue:
        puzzle, cnt = queue.popleft()
        
        if is_made(puzzle):
            is_not_found = False
            print(cnt)
            break
        
        
        temp = deserialize(puzzle)
        y, x = find_zero(temp)
        
        for dy, dx in [(0,1), (0,-1), (1,0), (-1,0)]:
            ny, nx = y + dy, x + dx
            if 3 > ny >=0 and 3 > nx >=0:
                table = deepcopy(temp)
                table[y][x], table[ny][nx] = table[ny][nx], table[y][x]
                check = serialize(table)
                if check not in visited:
                    visited.add(check)
                    queue.append((check, cnt + 1))
                    
    if is_not_found:
        print(-1)

solove(puzzle)