모든 숫자가 0에서 8 사이이고 반복되는 숫자가 없는 3x3 보드가 있다고 가정합니다. 이제 우리는 0을 4개의 이웃 중 하나로 바꿀 수 있으며 모든 정렬된 시퀀스를 얻기 위해 0을 해결하려고 하므로 목표에 도달하는 데 필요한 최소 단계 수를 찾아야 합니다.
따라서 입력이 다음과 같으면
| 3 | 1 | 2 |
| 4 | 7 | 5 |
| 6 | 8 | 0 |
그러면 출력은 4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- find_next() 함수를 정의합니다. 노드가 필요합니다.
- moves :=각 값 {0:[1, 3],1:[0, 2, 4],2:[1, 5],3:[0, 4]에 해당하는 목록으로 이동을 정의하는 맵 , 6],4:[1, 3, 5, 7],5:[2, 4, 8],6:[3, 7],7:[4, 6, 8],8:[5, 7 ],}
- 결과 :=새 목록
- pos_0 :=노드의 첫 번째 값
- 동작의 각 동작[pos_0]에 대해 다음을 수행합니다.
- new_node :=노드의 새 목록
- new_node[이동] 및 new_node[pos_0] 교체
- 결과 끝에 new_node에서 새 튜플 삽입
- 반환 결과
- get_paths() 함수를 정의합니다. 이것은 dict가 필요합니다
- cnt :=0
- 무한하게 다음을 수행합니다
- current_nodes :=값이 cnt와 동일한 목록
- current_nodes의 크기가 0과 같으면
- 반환 -1
- current_nodes의 각 노드에 대해 다음을 수행합니다.
- next_moves :=find_next(노드)
- next_moves의 각 이동에 대해 다음을 수행합니다.
- 이동이 dict에 없으면
- dict[이동] :=cnt + 1
- 움직임이 (0, 1, 2, 3, 4, 5, 6, 7, 8) 과 같으면
- cnt + 1을 반환
- cnt :=cnt + 1
- 이동이 dict에 없으면
- 기본 방법에서 다음을 수행합니다.
- dict :=새 지도, 병합 :=새 목록
- 보드의 행 수까지 범위 0에 있는 i에 대해
- flatten :=평평 + 보드[i]
- flatten :=flatten의 복사본
- dict[flatten] :=0
- flatten이 (0, 1, 2, 3, 4, 5, 6, 7, 8) 과 같으면
- 0을 반환
- get_paths(dict) 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution:
def solve(self, board):
dict = {}
flatten = []
for i in range(len(board)):
flatten += board[i]
flatten = tuple(flatten)
dict[flatten] = 0
if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return 0
return self.get_paths(dict)
def get_paths(self, dict):
cnt = 0
while True:
current_nodes = [x for x in dict if dict[x] == cnt]
if len(current_nodes) == 0:
return -1
for node in current_nodes:
next_moves = self.find_next(node)
for move in next_moves:
if move not in dict:
dict[move] = cnt + 1
if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return cnt + 1
cnt += 1
def find_next(self, node):
moves = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4, 6],
4: [1, 3, 5, 7],
5: [2, 4, 8],
6: [3, 7],
7: [4, 6, 8],
8: [5, 7],
}
results = []
pos_0 = node.index(0)
for move in moves[pos_0]:
new_node = list(node)
new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
results.append(tuple(new_node))
return results
ob = Solution()
matrix = [
[3, 1, 2],
[4, 7, 5],
[6, 8, 0]
]
print(ob.solve(matrix)) 입력
matrix = [ [3, 1, 2], [4, 7, 5], [6, 8, 0] ]
출력
4