[백준/1525/파이썬] 퍼즐

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

1525번: 퍼즐

Problem

우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다.

조건

• 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.
• 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다
• 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

SOL)

보기에는 엄청 간단해 보였던 문제였다.

그냥 단순히 0을 최소한의 횟수로 맨 아래로 옮겨보고, 정리가 되면 0이 움직인 횟수를 출력하면 되고, 아니면, 최소한의 이동으로 정리가 안되는거 아닌가 ? => 결론은, 아니였다.

왜냐하면, 정리하는 과정에서 언제든지 0을 끝으로 옮길 수 있기 때문에, 이 조건을 반례가 발생한다.

예제 입력 1이 운좋게 내가 생각했던 입력/출력이였음..

 

그래서, 결국 모든 경우를 다 봐야하고, 모든 경우에 대해서, 정리되어있는지 확인하는 방법을 떠올려야했지만, 사실 잘 떠오르지 않았고, index,dq에 정수를 넣는 아이디어 등 수많은 아이디어를 블로그를 통해서 알았다. 분발해야겠다.

 

• 3*3 배열을 마치, 문자열로 생각해서, 123456780 ( 코드에서는 편의상  0->9로 생각해줬다.)일 때, 정리가 되었다고 판단할 수 있다. 이 방법으로, 매번 2차원 board를 복잡하게 안돌수 있게 되었음.
• 즉, dq에는 123456789 처럼, 9자리 정수가 들어가게 된다.
• 그리고, 비어있는 칸(코드상에서는 9의 위치)를 2차원 board에 어디에 위치해 있는지 알아야함.그래야, bfs로 시뮬레이션을 돌릴 수 있게된다. 그래서, idx//3 (행), idx%3(열)이 된다. 1차원(n*n크기의 배열) ->2차원(단,n*n행렬일때) ,idx//n ->행,idx%n ->열이 되는건 몇 번 해보면 알게되는 사실이다.
• dictionary에 거리를 기록해주는 방법으로, dictionary에 해당 key에 대한 정보가 없으면, 등록해주고, 있으면, pass해주는 방법으로 구현했다.(BFS이므로, 최단거리가 보장되기 때문)

from collections import deque
dx=(1,0,-1,0)
dy=(0,1,0,-1)

def bfs():
    while dq:
        d = dq.popleft()
        if d == 123456789:
            print(dist[d])
            return
        s = str(d)
        idx=s.find('9')
        y,x = idx//3 , idx%3 # 행 = 나눈 값, 열 = 나머지
        for k in range(4):
            ny = y+dy[k] # 하나하나 바꿔보기.
            nx = x+dx[k] 
            if 0<=nx<3 and 0<=ny<3:
                # 바꾼 걸  일차원 배열 형식으로 바꿔서, board에 반영해줘야함.
                target_idx = 3*ny+nx
                ns = list(s)
                ns[target_idx],ns[idx] = ns[idx],ns[target_idx]
                nd = int(''.join(ns))
                if not dist.get(nd):
                    dist[nd]=dist[d] +1
                    dq.append(nd)
    print(-1)

dq = deque()
puzzle = [list(map(int,input().split())) for _ in range(3)]
dist={}
target=0
for i in range(3):
    for j in range(3):
        n= puzzle[i][j]
        if n==0:
            n=9
        target=target*10+n

dq.append(target)
dist[target]=0
bfs()