[BOJ] 퍼즐 in Python

문제풀러 가기!

요새 삼성 대비 문제를 좀 많이 풀고 있습니다. 개인적으로 삼성 문제의 경우 기초를 다지기 정말 좋은 문제들이 많다고 생각이 들어서 그런지 기초에 좀 더 치중해서 문제를 풀고 있습니다.

이번 문제는 사실 처음에는 감을 못잡았습니다. 어떤 방식으로 가야 풀릴지 생각을 하게되는 문제였기에 조금 더 머리를 쓸 수 밖에 없었습니다. 그래서 힌트를 좀 얻었습니다.

hashkey를 중심으로 bfs를 진행한다는 아이디어를 얻고 난 뒤에는 바로 풀게되었습니다.

제가 생각했던 문제의 idea는 다음과 같습니다.

문제에서 주어진 3X3행렬을 행으로 이어 붙여 하나의 hash 키로 만들어 hash키로 방문 여부를 체크한다.

그리고 델타이동을 활용해서 문자열로 이루어진 key값을 0을 기준으로 위치를 바꾸면서 bfs를 돌린다. 만약에 "123456780" 문자열이 나온다면, 탐색을 멈춘다.

물론 이를 위해서 생각할 아이디어는 2차원 배열의 인덱스 값을 1차원 배열로 옮겼을 때 어떻게 대응되는지 알아야 합니다. 0 인덱스를 알아야 하기 때문입니다. 그래서 index method를 활용했습니다.

코드를 자세히 보시면 그렇게 어렵게 작성한 것은 없습니다.

1. 방문 체크를 위한 visit: 다시는 방문한 곳은 다시는 방문하지 않기 위한 용도
2. delta이동 & 0인덱스: 2차원 배열 -> 1차원 배열로 대칭을 위한 용도
3. BFS: 탐색을 위한 용도

말고는 없습니다. 물론 Queue안에 무엇을 넣어야 하는지는 재량이기도 하며 저의 경우 새로운 키값과 최초키로부터 몇번을 움직여서 갔는지에 대한 count 값을 집어 넣었습니다.

아래는 풀이 코드입니다.

import sys
from collections import deque
input = sys.stdin.readline

arr = []
hash_key = ""
for _ in range(3):
    ele = list(map(int, input().split()))
    hash_key += "".join(list(map(str, ele)))


def bfs():
    queue = deque([(hash_key, 0)])
    visit = {
        hash_key: True
    }

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while queue:
        key, cnt = queue.popleft()

        if key == "123456780":
            return cnt

        zero = key.index("0")
        row = zero // 3
        col = zero % 3

        for i in range(4):
            nrow, ncol = row + dx[i], col + dy[i]
            if 0 <= nrow < 3 and 0 <= ncol < 3: 
                key_list = list(key)
                key_list[zero], key_list[3 * nrow + ncol] = key_list[3 * nrow + ncol], key_list[zero]
                new_key = "".join(key_list)
                if new_key in visit.keys():
                    continue
                else:
                    visit[new_key] = True
                    queue.append((new_key, cnt + 1))
    return -1

print(bfs())