Logic, State Space & Algorithms

논리 퍼즐 실험실

상태를 관찰하고 안전한 이동 순서를 찾아 다섯 가지 고전 퍼즐을 해결해 보세요.

개구리 점프

초록 개구리는 오른쪽으로, 갈색 개구리는 왼쪽으로만 이동합니다. 두 팀의 위치를 완전히 바꾸세요.

입문
개구리를 선택해 이동을 시작하세요.
이동 0회

규칙

  • 앞 칸이 비어 있으면 한 칸 이동할 수 있습니다.
  • 개구리 한 마리를 뛰어넘어 빈칸으로 이동할 수 있습니다.
  • 뒤로 이동할 수 없습니다.
Mathematical thinking

논리 퍼즐과 수학적 사고

퍼즐의 각 배치를 하나의 상태로 보고, 규칙을 만족하는 이동만 연결하면 문제 전체를 수학적인 상태 공간으로 표현할 수 있습니다.

상태 공간과 그래프

가능한 배치를 점, 가능한 이동을 선으로 나타내면 시작 상태에서 목표 상태까지의 경로를 찾는 그래프 문제가 됩니다.

개구리 점프의 규칙성

양쪽에 각각 N마리가 있을 때 최소 이동 횟수는 일정한 식으로 나타납니다.

최소 이동 횟수 = N(N + 2)

너비 우선 탐색

컴퓨터는 시작 상태에서 한 번에 갈 수 있는 모든 상태를 차례로 확장하는 BFS를 이용해 최소 이동 해답을 찾을 수 있습니다.