백준 1525. 퍼즐

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

from collections import deque

def solution():
    # 3x3 퍼즐 입력 받기
    start = ''
    for _ in range(3):
        start += ''.join(input().split())

    # 목표 상태
    target = "123456780"

    # 이동 방향 (상, 하, 좌, 우)
    directions = [-3, 3, -1, 1]

    # BFS 초기화
    queue = deque([(start, start.index('0'), 0)])  # (현재 상태, 0 위치, 이동 횟수)
    visited = set()
    visited.add(start)

    while queue:
        current, zero_pos, steps = queue.popleft()

        # 목표 상태 도달 시 종료
        if current == target:
            return steps

        # 0의 현재 위치를 기준으로 상하좌우 이동
        for d in directions:
            new_pos = zero_pos + d

            # 범위를 벗어나는 경우 무시
            if new_pos < 0 or new_pos >= 9:
                continue

            # 좌우 이동 시 같은 행인지 확인 (열 제약)
            if zero_pos % 3 == 0 and d == -1:  # 왼쪽 경계에서 좌측 이동
                continue
            if zero_pos % 3 == 2 and d == 1:  # 오른쪽 경계에서 우측 이동
                continue

            # 새로운 상태 생성
            new_state = list(current)
            new_state[zero_pos], new_state[new_pos] = new_state[new_pos], new_state[zero_pos]
            new_state = ''.join(new_state)

            # 방문하지 않은 상태라면 큐에 추가
            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, new_pos, steps + 1))

    # 목표 상태에 도달할 수 없는 경우
    return -1

# 결과 출력
print(solution())

[핵심 포인트]

1. 문자열로 치환 

2. 0을 이동시킨다!

3. 문자열로 치환했으므로 이동시 열이 바뀔 때 주의해서 예외처리

4. visited를 set으로 설정

5. 문자열->리스트->자리바꾸기->문자열 ----> 후 set(visited)에 방문처리