BOJ(퍼즐)(1525)

작성일 | In

퍼즐 1525

  • 8퍼즐을 푸는 문제
  • 3*3 크기고 1~8크기.
  • 인접한 칸만 이동할 수 있다.
  • 12345678 빈칸을 만들어주는 게 퍼즐의 목표다.

  • 퍼즐을 그냥 푸는건 아니고, 최소 몇번 만에 퍼즐을 풀 수 있는지 구하는 문제다.

  • BFS 문제인지 확인
  • 시작점에서 도착점으로 가는 최단거리를 구하는 문제와 같다.
  • 그 때, 최소 연산횟수를 구하라고 했는데, 각각의 연산의 가중치가 모두 1이다.

  • 그럼 BFS 문제가 맞다.

  • ※ 가중치가 1이지만 BFS 문제가 아닐 수도 있다 -> 정점의 개수가 너무 많을 때.

  • 정점의 개수가 몇 개일까? -> 서로다른 퍼즐의 개수. 9!개가 나온다.

  • 1부터 9까지의 수를 중복없이 채워넣는 경우의 수와 같기 때문이다. => 30만개의 정점이면 그렇게 많은게 아니다.

  • 절대로 퍼즐을 풀 수 없는 경우도 있다.
  • 12345687인 경우다.

  • 그래서 실제 정점의 개수는 이것보다 더 작은 값이 나온다.

  • 9자리 정수를 넣을려면, 크기가 10억인 배열이 필요하다. 10억은 큰수다. 공간에 대한 고려 필요
  • 인트-> 4바이트 ->10억 -> 40억 바이트가 나온다.
  • 40 - 2^30 -> 4기가바이트.
  • 저장해야하는 것은 30만개. 정확하게 30만개만 쓰는 방법은 ?
  • map이란 것을 이용하면 된다.배열은 배열인데 정수가 아닌 문자열 또는 배열을 넣을 수 있는 자료구조라고 생각하면 된다.
  • 구현이 조금 까다로운 문제다.
  • 우선 스킵해도 좋은 문제
from collections import deque
dx = [0,0,1,-1]# 상하좌우
dy = [1,-1,0,0]
n = 3 # 항상 n은 3
a = [list(map(int,input().split())) for _ in range(n)]
start = 0
for i in range(n):
    for j in range(n):
        if a[i][j] == 0:
            a[i][j] = 9
        start = start * 10 + a[i][j] # 9자리 정수로 바꿔주는 과정
q = deque() # bfs
dist = dict() # map(python에서는 dictionary)
dist[start] = 0
q.append(start)
while q:
    now_num = q.popleft() # now_num에는 3*3의 상태가 정수로 들어있다.
    now = str(now_num) # now에는 문자열로 들어있다.
    z = now.find('9') # 빈칸의 위치
    x = z//3 # 빈칸의 위치가 x행
    y = z%3 # y열 임을 알 수 있다.
    for k in range(4):
        nx,ny = x+dx[k], y+dy[k] # 이동은 위치를 바꾸는 것을 볼 수 있다.
        if 0 <= nx < n and 0 <= ny < n:
            temp = list(now)
            temp[x*3+y],temp[nx*3+ny] = temp[nx*3+ny],temp[x*3+y]
            num = int(''.join(temp))
            if num not in dist:
                dist[num] = dist[now_num] + 1
                q.append(num)
if 123456789 in dist:
    print(dist[123456789])
else:
    print(-1)

참고자료 codeplus

0%