[BaekJoon] 1525 퍼즐

🔦 문제 링크

✍️ 나의 풀이

첫 풀이 때 메모리 제한이 있다는 걸 알았지만 3x3 배열의 상태를 큐로 넣어서 넘기려고 했고 당연히 메모리 초과가 발생했다.
메모리 초과를 피하기 위해선 리스트로 위치를 표현하는 방법 대신 문자열로 위치 상태를 표현해야 한다.

• 문자열을 통한 위치 상태 기록 및 방문 파악
• 2차원 배열을 1차원으로 표현하기

🛠 나의 코드

from collections import deque


def BFS(sx, sy, ch):
    q = deque()
    q.append((sx, sy, ch, 0))

    while q:
        tx, ty, ch, count = q.popleft()
        if "123456789" == ch:
            return count
        for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
            nx, ny = tx + dx, ty + dy
            if 0 <= nx < 3 and 0 <= ny < 3:
                a = list(ch)
                tmp = a[tx*3 + ty]
                a[tx*3 + ty] = a[nx*3 + ny]
                a[nx*3 + ny] = tmp
                c = ''.join(a)
                if not dict_check.get(c):
                    dict_check[c] = 1
                    q.append((nx, ny, c, count+1))
    return -1


arr = [input().split() for _ in range(3)]
check = []
start_x, start_y = 0, 0
dict_check = dict()
for i in range(3):
    for j in range(3):
        if arr[i][j] == '0':
            arr[i][j] = '9'
            start_x = i
            start_y = j
        check.append(arr[i][j])
check = ''.join(check)
dict_check[check] = 1
print(BFS(start_x, start_y, check))

✍️ 다른 사람 풀이

큐에 오직 현재 위치 상태를 표시하는 숫자만 넣는다.
다음 시작 위치는 find('9')를 통해 찾는다.
또한, 방문여부 체크와 이동 횟수를 동시에 기록한다.

🛠 다른 사람 코드

...
k = s.find('9')  # 9의 index 탐색
        x, y = k // 3, k % 3
        for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):  # 0~3
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= 3 or ny < 0 or ny >= 3:
                continue
            nk = nx*3 + ny  # 바꿀 위치
            ns = list(s)
            ns[k], ns[nk] = ns[nk], ns[k]  # 리스트를 통한 swap 식
            nd = int(''.join(ns))  # 다시 문자열로..
            if not dist.get(nd):  # 방문 여부 확인
                dist[nd] = dist[d] + 1  # 이전 위치에서 + 1
                q.append(nd)
...

📝 정리

• 문자열을 통해 현재 위치 배열을 적은 메모리로 저장할 수 있다.

🎈 참고

rebas님 블로그