[ 1525 ] [ BFS ] 퍼즐

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

1525번: 퍼즐

 

---

풀이 과정

---

1. 일반적인 BFS 문제들과 비슷
   • 현재 0의 위치가 X,Y라고 할 때, 0의 위치로 이동할 수 있는 점은 (X-1,Y)에서, (X, Y-1)에서, (X+1, Y)에서, (X, Y+1)에서 총 네가지 경우라고 볼 수 있음. 물론 배열의 범위를 벗어나게 되는 경우는 제외해야 함.
2. 어려웠던 점은.. 메모리 초과 문제
   • 한번 방문했던 지점을 다시 방문하지 않도록 하기 위해 저장을 해야 하는데, 방문한 2차원 배열을 그대로 저장하면 메모리 초과 문제가 나타남.
   • 따라서, 방문 기록과 큐에 저장할 때 문자열 형태로 저장, 예시로 [[1,2,3], [4,5,6], [7,8,0]]인 경우, 123456780으로 저장한 다음, 큐에서 꺼낼 때 다시 2차원 배열 형태로 바꿔줌.
3. 데이터를 저장할 때는 메모리를 최대한 아끼는 쪽으로 저장해야 됨.

 

---

소스 코드

---

 

import sys
import copy
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

matrix = [list(map(int, input().split())) for _ in range(3)]

def find_0(matrix):
    for i in range(3):
        for j in range(3):
            if matrix[i][j] == 0:
                return [i, j]
    return None

def check_finish(matrix):
    answer = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    for i in range(3):
        for j in range(3):
            if answer[i][j] != matrix[i][j]:
                return False
    return True

def atos(matrix):
    result = ''
    for i in range(3):
        for j in range(3):
            result += str(matrix[i][j])
    return result

def stoa(string):
    return [[int(string[3*i+j]) for j in range(3)] for i in range(3)]

def bfs(matrix):
    visited = set([atos(matrix)])
    queue = deque()
    queue.append([atos(matrix), 0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        mat, movement = queue.popleft()
        mat = stoa(mat)
        if check_finish(mat):
            return movement
        x, y = find_0(mat)
        for i in range(4):
            target_x = x + dx[i]
            target_y = y + dy[i]
            if target_x >= 0 and target_x < 3 and target_y >= 0 and target_y < 3:
                mat[x][y], mat[target_x][target_y] = mat[target_x][target_y], mat[x][y]
                if atos(mat) not in visited:
                    visited.add(atos(mat))
                    queue.append([atos(mat), movement+1])
                mat[x][y], mat[target_x][target_y] = mat[target_x][target_y], mat[x][y]
    
    return -1

print(bfs(matrix))