문제 소개
0부터 8까지의 숫자가 중복 없이 하나씩 배치된 3×3 보드가 있다고 가정해 봅시다. 숫자 0은 상하좌우로 인접한 칸의 숫자와 자유롭게 맞바꿀 수 있습니다. 목표는 보드의 모든 숫자를 순서대로 정렬된 상태로 만드는 것이며, 이때 필요한 최소 이동 횟수를 구해야 합니다.
예를 들어 입력 보드가 다음과 같다면,
| 3 | 1 | 2 |
| 4 | 7 | 5 |
| 6 | 8 | 0 |
출력은 4가 됩니다.
접근 방법: 너비 우선 탐색(BFS)
8-퍼즐은 그래프 탐색 문제로 바꿔 생각할 수 있습니다. 보드의 각 상태를 하나의 노드로 보고, 0을 한 칸 움직일 때마다 인접한 상태로 이동한다고 가정하면, 시작 상태에서 목표 상태까지의 최단 경로를 찾는 문제가 됩니다. 모든 이동의 비용이 동일하므로 너비 우선 탐색(BFS)을 사용하면 최소 이동 횟수를 보장받을 수 있습니다.
1단계: find_next() 함수 — 이동 가능한 다음 상태 생성
현재 보드 상태(node)를 받아, 0을 한 번 이동했을 때 나올 수 있는 모든 상태를 반환하는 함수입니다.
- moves 맵을 정의합니다. 각 인덱스(위치)마다 0이 이동할 수 있는 인접 인덱스 목록을 저장합니다. 예를 들어 모서리에 있는 0은 두 방향으로만, 가운데에 있는 0은 네 방향으로 이동할 수 있습니다.
- 결과를 담을 새 리스트 results를 준비합니다.
- pos_0은 현재 노드에서 0이 있는 위치입니다.
- moves[pos_0]의 각 이동 후보에 대해 다음을 반복합니다.
- node를 복사해 new_node를 만듭니다.
- new_node[move]와 new_node[pos_0]의 값을 서로 교환합니다.
- 교환 결과를 튜플로 만들어 results 끝에 추가합니다.
- 완성된 results를 반환합니다.
2단계: get_paths() 함수 — BFS로 최소 단계 탐색
방문한 상태와 해당 상태까지의 이동 횟수를 딕셔너리(dict)에 기록하면서, 단계별로 넓게 탐색을 진행합니다.
- cnt를 0으로 초기화합니다.
- 무한 루프를 돌며 다음을 수행합니다.
- current_nodes는 dict에서 값이 cnt와 같은 상태들의 목록입니다. 즉, 현재 단계(cnt번 이동)에 도달한 모든 상태를 의미합니다.
- current_nodes가 비어 있다면 더 이상 탐색할 상태가 없다는 뜻이므로 -1을 반환합니다. 이는 목표 상태에 도달할 수 없는 경우입니다.
- current_nodes의 각 노드에 대해 다음을 수행합니다.
- find_next()를 호출해 다음에 이동 가능한 상태들을 구합니다.
- 각 이동(move)이 dict에 아직 없는 새로운 상태라면 dict[move] = cnt + 1로 기록합니다.
- move가 목표 상태 (0, 1, 2, 3, 4, 5, 6, 7, 8)와 같다면 cnt + 1을 반환합니다.
- 현재 단계의 모든 노드 처리가 끝나면 cnt를 1 증가시킵니다.
3단계: solve() 메서드 — 전체 실행 흐름
- 빈 딕셔너리 dict와 빈 리스트 flatten을 준비합니다.
- 보드의 각 행을 순회하면서 flatten에 요소들을 이어 붙여, 2차원 보드를 1차원 리스트로 펼칩니다.
- flatten을 튜플로 변환하고, dict[flatten] = 0으로 시작 상태를 기록합니다.
- flatten이 이미 목표 상태 (0, 1, 2, 3, 4, 5, 6, 7, 8)라면 0을 반환합니다.
- 그렇지 않으면 get_paths(dict)를 호출해 결과를 반환합니다.
구현 코드
아래는 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.
class Solution:
def solve(self, board):
dict = {}
flatten = []
for i in range(len(board)):
flatten += board[i]
flatten = tuple(flatten)
dict[flatten] = 0
if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return 0
return self.get_paths(dict)
def get_paths(self, dict):
cnt = 0
while True:
current_nodes = [x for x in dict if dict[x] == cnt]
if len(current_nodes) == 0:
return -1
for node in current_nodes:
next_moves = self.find_next(node)
for move in next_moves:
if move not in dict:
dict[move] = cnt + 1
if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return cnt + 1
cnt += 1
def find_next(self, node):
moves = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4, 6],
4: [1, 3, 5, 7],
5: [2, 4, 8],
6: [3, 7],
7: [4, 6, 8],
8: [5, 7],
}
results = []
pos_0 = node.index(0)
for move in moves[pos_0]:
new_node = list(node)
new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
results.append(tuple(new_node))
return results
ob = Solution()
matrix = [
[3, 1, 2],
[4, 7, 5],
[6, 8, 0]
]
print(ob.solve(matrix))
입력
matrix = [ [3, 1, 2], [4, 7, 5], [6, 8, 0] ]
출력
4
마무리 및 참고 사항
BFS의 특성상 각 상태를 처음 발견했을 때 기록된 이동 횟수가 곧 최소 이동 횟수임이 보장됩니다. 또한 8-퍼즐에는 순열의 역전(inversion) 개수에 따라 목표 상태에 도달할 수 없는 초기 배치도 존재하는데, 이런 경우 탐색할 상태가 고갈되어 -1이 반환되므로 해결 가능 여부까지 함께 판별할 수 있습니다.
한 가지 팁을 덧붙이자면, 예제 코드에서는 변수 이름으로 dict를 사용했지만 실제 프로젝트에서는 파이썬 내장 타입 dict와의 충돌을 피하기 위해 visited처럼 의미가 명확한 다른 이름을 사용하는 것이 좋습니다.