문제

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

1 2 3
4 5 6
7 8  

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

1   3
4 2 5
7 8 6
1 2 3
4   5
7 8 6
1 2 3
4 5  
7 8 6
1 2 3
4 5 6
7 8  

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

www.acmicpc.net/problem/1525

  • 입력

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

  • 출력

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

최종코드

요새 계속 완전탐색 문제를 풀어서 bfs와 완전탐색을 통해 풀어야겠다고 생각했다. 근데 퍼즐을 어떻게 방문처리해야 효율적으로 할 수 있을지 생각이 안 났다.

그래서 찾아본 결과 퍼즐은 문자열로 나타내고, visit은 사전으로 선언하면 효율적으로 처리할 수 있다는 것을 알게 되었다. visit["123456780"] = 1 과 같이 처리하면 된다.

또 다른 문제는 “123456780”과 같이 퍼즐을 문자열로 나타낼 경우 두 칸을 어떻게 swap하느냐 하는 문제였다. 이 부분은 아래 swap 함수 코드를 보면 된다. 잘 봐뒀다가 필요할 때 고민없이 쓰고싶다!

import sys
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# 문자열에서 index가 a와 b인 문자를 swap하는 함수
def swap(s, a, b):
    c = s[a]
    d = s[b]
    s = s[:b] + c + s[b+1:]
    s = s[:a] + d + s[a+1:]
    return s

def bfs():
    global puzzle
    q = deque()
    q.append([puzzle, 0])
    visit = dict() # 방문 확인은 사전으로
    visit[puzzle] = 1

    while q:
        now, cnt = q.popleft()
        # 답을 찾은 경우 이동 횟수 반환
        if now == "123456780":
            return cnt
        pos = now.find("0") # 0의 위치
        row = pos // 3 # 행
        col = pos % 3 # 열

        for i in range(4):
            x = row + dx[i]
            y = col + dy[i]
            if x < 0 or x >= 3 or y < 0 or y >= 3:
                continue
            # swap 함수를 통해 퍼즐 이동
            new = swap(now, pos, x * 3 + y)
            # 방문한 적이 없다면 계속 탐색
            if visit.get(new) == None:
                visit[new] = 1
                q.append([new, cnt + 1])
    return -1

puzzle = ""
for _ in range(3):
    puzzle += "".join(sys.stdin.readline().strip().split())
print(bfs())

참고 사이트