[백준] 1525번: 퍼즐 / Python / 너비우선탐색(BFS)

퍼즐

• 문제
  3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

  1	2	3
  4	5	6
  7	8

  어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

  1		3
  4	2	5
  7	8	6

  1번 이동

  1	2	3
  4		5
  7	8	6

  2번 이동

  1	2	3
  4	5
  7	8	6

  3번 이동

  1	2	3
  4	5	6
  7	8

  가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

• 입력
  세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

• 출력
  첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

나의 풀이

• 퍼즐의 모양이 2차원 배열이라고 해서 2차원 배열을 이용하면 문제가 상당히 복잡해진다. 빈칸을 0으로 두고, 퍼즐을 문자열 '123456780'으로 정렬시킨다고 생각하자.
• 방문 여부를 체크하는 방법이 생각하기 쉽지 않다. 리스트에 저장하는 것만 해봤었는데 이 문제 같은 경우는 딕셔너리를 이용하면 빠르고 쉽다. {key:value} = {퍼즐의 모습:이동 횟수}로 저장하자. (퍼즐의 모습을 key로 사용하기 위해서라도 2차원 배열이 아닌 문자열을 이용해야 한다.)
• 퍼즐의 모습을 문자열로 바꾸면 0(빈칸)을 이동시킬 때 다시 2차원 배열의 위치를 생각해주어야 한다. 문자열(1차원 리스트)에서 0의 인덱스 찾기 → 2차원 배열의 행, 열 인덱스로 변환 → 상하좌우 방향으로 이동 가능 여부 체크 → 이동시킬 수 있다면 2차원 배열에서의 새 위치를 다시 문자열에서의 인덱스로 변환 → 해당 위치로 0 이동의 과정이 필요하다.
• 새 위치로 0을 이동시킬 때는 리스트 원소 스와핑을 이용하고 딕셔너리로 방문 여부를 체크하면서 bfs를 진행하면 된다.

from collections import deque

# 퍼즐을 문자열 123456780로 정렬시킨다고 생각하자
puzzle = ""
for i in range(3):
    puzzle += "".join(list(input().split()))

# 현재 puzzle의 모습을 key로, 움직인 횟수를 value로 저장
visited = {puzzle:0}
q = deque([puzzle])

# 상하좌우로 0(빈칸)을 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
    while q:
        puzzle = q.popleft()
        cnt = visited[puzzle]
        z = puzzle.index('0') # 0(빈칸)의 위치
        
        if puzzle == '123456780':
            return cnt
        
        x = z // 3 # 2차원 배열의 행
        y = z % 3 # 2차원 배열의 열
        
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <= 2 and 0 <= ny <= 2: # 이동 가능한 위치일 경우
                # nx, ny를 다시 리스트의 인덱스로 바꾸자
                nz = nx * 3 + ny
                puzzle_list = list(puzzle) # 원소 스와핑을 위해 문자열을 리스트로 바꾸자
                puzzle_list[z], puzzle_list[nz] = puzzle_list[nz], puzzle_list[z]
                new_puzzle = "".join(puzzle_list) # 딕셔너리를 위해 다시 문자열로
                
                # 방문하지 않았다면
                if visited.get(new_puzzle, 0) == 0:
                    visited[new_puzzle] = cnt 
                    q.append(new_puzzle)
                    
    return -1
                    
print(bfs())