[백준] 1525번 - 퍼즐 (파이썬)

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

# 퍼즐
from collections import deque
N = 3
arr = []
zero_x = 0
zero_y = 0
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] == 0:
            zero_x = i
            zero_y = j
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
visit = dict()


def bfs(a, b):
    global arr
    q = deque()
    string = change(arr)
    if string == '123456780':
        return '0'
    q.append((a, b, 0, string))
    visit[string] = True
    while q:
        x, y, count, string = q.popleft()
        if string == '123456780':
            return count
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < N:
                index = x*3+y
                next_index = nx*3+ny
                next_string = list(string)
                next_string[index] = next_string[next_index]
                next_string[next_index] = '0'
                next_string = ''.join(next_string)
                if not visit.get(next_string):
                    visit[next_string] = True
                    q.append((nx, ny, count+1, next_string))
    return False


def change(arr):
    string = ''
    for i in range(N):
        for j in range(N):
            string += str(arr[i][j])
    return string


result = bfs(zero_x, zero_y)
if result:
    print(result)
else:
    print(-1)

 

BFS

1. 입력을 받으면서 0의 위치를 기억해준다.

2. 0의 위치를 시작으로 bfs실행

    - 큐에 (x좌표, y좌표, 움직인횟수, 현재문자열)을 넣어준다.

    - 현재 문자열이 '123456780'이면 return count

    - 다음문자열 = 상하좌우를 탐색하면서 문자열일 때의 index값들을 구해주고 두자리를 바꿔준다.

    - 해당 문자열이 딕셔너리에 없으면 딕셔너리에 넣어주고 q.append

3. 값 출력

 

아이디어를 떠올리는게 어려웠다.

첫째, 해당 배열을 문자열로 비교하는 것

둘째, 해당 문자열의 방문여부를 딕셔너리로 관리 할 것 (시간초과 예방)

셋째, 배열의 x,y좌표를 문자열의 단일 좌표로 바꾸기

 

100%에서 틀렸다고 나와서 1시간동안 찾았지만 답은 처음에 입력된 값이 답일 경우였다.

그래서 급하게 처음 입력하면 change함수를 통해서 string으로 반환해서 return '0'을 해주었다.

울고싶다..