퍼즐[백준1525] - python

 

배열 자체를 bfs에 넣고 매번 꺼낸 배열을 string으로 변환해서 비교를 하려고 시도했었다가. 이건 아니다 싶어서

bfs에 문자열을 넣고 x,y의 좌표를 이용해서 배열에서 바꿔야 하는 0의 인덱스를 계산해서 다음 값과 바꿔주는 형식으로 시도했었다.

근데 이 방법은 메모리 부족으로 통과 하지 못했고.

결국 다른 분들의 코드를 참고했다.

 

정답코드 먼저 살펴보자

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs():
  while q:
    now = q.popleft()
    if now == "123456789":
      return cntDict[now]
    pos = now.find("9")
    x = pos // 3
    y = pos % 3
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < 3 and 0 <= ny < 3:
        nPos = nx * 3 + ny
        nextNum = list(now)
        nextNum[nPos], nextNum[pos] = nextNum[pos], nextNum[nPos]
        nextNum = "".join(nextNum)

        if not cntDict.get(nextNum):
          q.append(nextNum)
          cntDict[nextNum] = cntDict[now] + 1

start = ""
for _ in range(3):
  temp = sys.stdin.readline().strip()
  temp = temp.replace(" ", "")
  start += temp

start = start.replace("0", "9")

q = deque()
q.append(start)

cntDict = dict()
cntDict[start] = 0

result = bfs()
print(result if result != None else "-1")

 

python dict()의 사용법에 대해서 알아봐야겠다.

dict.get(x) 메소드와 비슷한 케이스를 자주 사용해서 알아두어야 겠다.

 

예제는 나오지만 메모리가 초과해서 풀지 못한 코드

from collections import deque
import sys
def BOJ1525() :
  graph = []
  answer = "123456780"
  queue = []
  visited = {}
  direction = [[0,1], [0,-1], [1,0], [-1,0]]
  result = -1
  for _ in range(3) :
    for i in input().split() :
      graph.append(i)
  
  serialized_graph = graph
  start_index = serialized_graph.index("0")
  start_x, start_y = divmod(start_index, 3)
  visited["".join(serialized_graph)] = True
  queue.append(["".join(serialized_graph), 0, start_x, start_y])

  while queue:
    current_graph, count, curr_x, curr_y = queue.pop(0)

    if current_graph == answer:
      result = count
      break
    curr_location = curr_x * 3 + curr_y
    
    for dir_x, dir_y in direction :
      next_x = curr_x + dir_x
      next_y = curr_y + dir_y
      next_location = next_x * 3 + next_y
      if 0 <= next_x <= 2 and 0 <= next_y <= 2 :
        temp_graph = list(current_graph)
        temp_graph[next_location], temp_graph[curr_location] = temp_graph[curr_location], temp_graph[next_location]
        join_graph = "".join(temp_graph)
        if join_graph not in visited:
          visited[join_graph]=True
          queue.append([join_graph, count+1, next_x, next_y])

  print(result)

BOJ1525()

 

 

 

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

1525번: 퍼즐

 

출처: https://cijbest.tistory.com/15