[백준1525] 퍼즐

문제

---

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

1525번: 퍼즐

 

생각의 흐름

---

1. 메모리 제한이 심한 문제이다. 따라서 2차원 리스트 그대로를 이용해 문제를 풀기에는 무리가 있다. 메모리 제한을 해결하기 위해선 저장하는 방식을 바꾸어야 하는데 주어진 예시에서 0을 9로 바꿔주고 이를 int형으로 저장한다. 예를 들어 예제1의 경우 193425786이 된다.
2. 위와 같이 저장하면 특정한 "상태"를 나타낼 수 있는데 이 상태에 대한 value 값으로 이동 횟수를 매칭시켜 저장해야 한다. 이를 위해 dictionary 구조를 사용한다. 즉, key:value = 특정수:옮긴 횟수가 되는 것이다.
3. 각 상태에서 '9'가 이동가능한 경우는 상하좌우 4가지이다. 각 경우에 대해 4가지의 경우를 탐색하면서 q에 넣어주고 다시 그 경우들에 대해 같은 방식으로 탐색을 하면 가능한 모든 경우에 대해 탐색이 가능하다.(BFS)

 

깨달은 점

---

BFS를 자꾸만 그래프나 트리 구조와 연관지어서만 사용하려고 하는 경우가 있다. 하지만 BFS의 핵심은 그저 "탐색"의 한 방법이라는 것이다. 이 때 말하는 탐색이란 queue에서부터 하나씩 빼서 해당 경우에서 가능한 경우들을 탐색해 다시 queue에 넣고, 여기서 하나씩 빼면서 동일한 과정을 반복한다는 것이다!!!

 

코드

---

# BOJ 1525
from collections import deque

def bfs():
    while q:
        d = q.popleft()
        if d == 123456789:
            print(dist[d])
            return
        s=str(d)
        zero=s.find('9')
        # x는 행 y는 열
        x,y = zero//3, zero%3
        for dx, dy in (1,0), (-1,0), (0,1), (0,-1):
            nx, ny = x+dx, y+dy
            if 0<=nx<3 and 0<=ny<3:
                k = nx*3+ny
                ns = list(s)
                ns[k], ns[zero] = ns[zero], ns[k]
                nd = int(''.join(ns))
                if not dist.get(nd):
                    dist[nd]=dist[d]+1
                    q.append(nd)
    print(-1)


q = deque()
# dist의 key:value=정수:옮긴횟수
dist = {}
puzzle = [list(map(int, input().split())) for _ in range(3)]
m=0
for i in range(3):
    for j in range(3):
        n = puzzle[i][j]
        if n==0:
            n=9
        m = m*10 + n
q.append(m)
dist[m]=0
bfs()