. 슬라이딩 퍼즐

773. 슬라이딩 퍼즐

난이도:어려움

주제: 배열, 너비 우선 검색, 행렬

2 x 3 보드에는 1부터 5까지 표시된 5개의 타일과 0으로 표시되는 빈 사각형이 있습니다. 이동은 0과 4방향으로 인접한 숫자를 선택하고 교체하는 것으로 구성됩니다. .

보드의 상태는 보드가 [[1,2,3],[4,5,0]]인 경우에만 해결됩니다.

퍼즐보드 보드가 주어지면 보드 상태를 해결하는 데 필요한 최소한의 이동 횟수를 반환합니다. 보드의 상태를 해결하는 것이 불가능할 경우 -1을 반환합니다.

예 1:

• 입력: 보드 = [[1,2,3],[4,0,5]]
• 출력: 1
• 설명: 한 번에 0과 5를 바꿉니다.

예 2:

• 입력: 보드 = [[1,2,3],[5,4,0]]
• 출력: -1
• 설명: 아무리 움직여도 보드가 해결되지 않습니다.

예 3:

• 입력: 보드 = [[4,1,2],[5,0,3]]
• 출력: 5
• 설명: 5는 보드를 해결하는 가장 작은 수입니다.
  • 예제 경로:
  • 0번 이동 후: [[4,1,2],[5,0,3]]
  • 이동 1 후: [[4,1,2],[0,5,3]]
  • 2번째 이동 후: [[0,1,2],[4,5,3]]
  • 3번째 이동 후: [[1,0,2],[4,5,3]]
  • 4번째 이동 후: [[1,2,0],[4,5,3]]
  • 5번째 이동 후: [[1,2,3],[4,5,0]]

제약조건:

• board.length == 2
• board[i].length == 3
• 0 <= 보드[i][j] <= 5
• 각 값 보드[i][j]는 고유합니다.

힌트:

1. 한 번의 움직임으로 두 개의 퍼즐 보드가 서로 변환될 수 있는 경우 노드가 퍼즐 보드이고 가장자리가 가장자리인 너비 우선 검색을 수행합니다.

해결책:

BFS(Breadth-First Search) 알고리즘을 적용할 수 있습니다. 주어진 초기 상태부터 해결된 상태에 도달할 때까지 한 번에 한 동작씩 보드의 가능한 모든 구성을 탐색하는 것이 아이디어입니다.

접근하다:

1. BFS(너비 우선 검색):

   • 해결된 상태로 가는 최단 경로를 찾기 때문에 BFS가 이상적입니다.
   • 각 보드 구성은 노드로 간주될 수 있으며, 노드 사이의 가장자리는 0 타일이 인접한 타일과 교체되는 유효한 이동을 나타냅니다.
   • BFS는 최소한의 이동 횟수로 해결 상태에 도달할 수 있도록 레벨별로 보드 구성을 탐색합니다.

2. 주 대표:

   • 보드를 문자열로 표현하겠습니다(비교 및 저장이 용이함).
   • 해결된 상태는 보드 [[1,2,3],[4,5,0]]의 선형 표현이므로 "123450"입니다.

3. 상태 전환:

   • 각 상태에서 0 타일은 보드 경계 내에 있는 경우 인접한 4개 타일(위, 아래, 왼쪽, 오른쪽) 중 하나와 교체될 수 있습니다.

4. 방문 상태 추적:

   • 주기와 중복 계산을 피하기 위해 방문한 상태를 추적해야 합니다.

5. 해결 상태 확인:

   • 언제든지 보드 구성이 해결된 상태와 일치하면 거기에 도달하는 데 걸린 이동 횟수를 반환합니다.

6. 불가능한 사례 처리:

   • BFS가 완료되고 해결된 상태를 찾지 못하면 퍼즐을 풀 수 없다는 의미이며 -1을 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다. 773. 슬라이딩 퍼즐

  
  
  설명:




초기 설정: 더 쉬운 조작을 위해 2D 보드를 1D 스트링으로 변환하는 것부터 시작합니다.

BFS 실행: 이동 횟수(0부터 시작)와 함께 보드의 초기 상태를 대기열에 추가합니다. 각 BFS 반복에서 가능한 이동을 탐색하고(0 타일의 위치를 ​​기준으로) 0을 인접한 타일과 교환하고 새 상태를 대기열에 추가합니다.

방문 상태: 동일한 상태를 다시 방문하거나 반복하는 것을 방지하기 위해 사전을 사용하여 방문한 보드 상태를 추적합니다.

가장자리 유효성 검사: 모든 이동이 2x3 그리드 범위 내에 있는지 확인합니다. 특히 그리드 주위를 둘러싸는 불법적인 이동(예: 왼쪽 가장자리에서 왼쪽으로 이동하거나 오른쪽 가장자리에서 오른쪽으로 이동)이 없는지 확인합니다. 

반환 결과: 목표 상태에 도달하면 이동 횟수를 반환합니다. BFS가 완료되고 목표에 도달하지 못하면 -1을 반환합니다.



  
  
  시간 복잡도:




BFS 복잡도: BFS의 시간 복잡도는 O(N)입니다. 여기서 N은 고유한 보드 상태의 수입니다. 이 퍼즐에는 최대 6개가 있습니다! (720) 구성이 가능합니다.



  
  
  공간 복잡도:



큐와 방문 상태에 필요한 저장 공간으로 인해 공간 복잡도도 O(N)입니다.


이 솔루션은 제약 조건을 고려할 때 충분히 효율적이어야 합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 . 슬라이딩 퍼즐의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!