1525번 퍼즐

문제 설명

1525번: 퍼즐

 

나의 풀이

from collections import deque, defaultdict


def bfs(start_num):
    cnt_dict = defaultdict(int)
    q = deque()
    q.append(start_num)

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

    while q:
        cur_num = q.popleft()

        if cur_num == '123456780':
            return cnt_dict[cur_num]

        zero_idx = cur_num.find('0')
        zero_x = zero_idx // 3
        zero_y = zero_idx % 3
        for i in range(4):
            zero_nx = zero_x + dx[i]
            zero_ny = zero_y + dy[i]

            if 0<=zero_nx<3 and 0<=zero_ny<3:
                next_zero_idx = (zero_nx * 3) + zero_ny
                next_num = list(cur_num)
                next_num[zero_idx], next_num[next_zero_idx] = next_num[next_zero_idx], next_num[zero_idx]
                next_num = ''.join(next_num)
                
                if not cnt_dict[next_num]:
                    cnt_dict[next_num] = cnt_dict[cur_num] + 1
                    q.append(next_num)
                
            
start_num = ''
for _ in range(3):
    start_num += input()
start_num = start_num.replace(" ", "")

result = bfs(start_num)
if result != None:
    print(result)
else:
    print(-1)

참고 블로그

https://cijbest.tistory.com/15

[백준 1525 : PYTHON] 퍼즐

문제 핵심

- 변환되는 상태를 문자열로 받아서 딕셔너리의 키로 그리고 해당 초기 값에서 얼마나 변했는지에 대한 카운트를 밸류로 두는 것.

- 문자열의 인덱스(문자열.find(val)함수)와 퍼즐 형태의 이중리스트의 행렬 값을 구하고 행렬값에 따른 인덱스 범위 설정.

 

** 놓쳤던 부분

마지막 if 조건절에서 값이 0이 나오는것을 미쳐 생각 못하고 if result:라고 했다. -> if result != None: 으로 정확히 구분할 필요가 있다.