itisMilob

GooApp - 퍼즐 교착상태 문제점

2025-06-02
퍼즐을 만들며 발생한 문제점 해결과정

상황

퍼즐을 만들면서 교착상태에 빠져 더이상 진행할 수 없는 문제가 발생했다.

원하는 기능은 5:5로 문제와 정답을 연결하는 기능이다.

  • 문제, 정답이 이전과 다른 랜덤한 위치에 떠야 한다.
  • 항상 연결할 수 있는 문제-정답 조합이 하나 이상 남아있어야 한다.

첫 접근 방식

처음에는 문제-정답이 모두 이어지는 그룹을 계속 쌓아가는 스택 방식을 생각했다.

  • 버튼의 개수대로 문제들을 모아놓은 그룹을 만든다. - 이 그룹이 1개 층이 된다.
  • 문제를 맞추면 다음 스택에 있는 문제가 올라온다.
  • 윗층을 모두 맞추면 아래층으로 완전히 넘어가면서 항상 조합이 나오도록 유지된다.

시각화 예시

  • 맞춘 문제는 사라진다.
  • 다음 스택의 문제들이 보여진다.

예시 상황

하나의 정답에 연결될 수 있는 두 개의 정답이 존재할 수 있다.

다른 층의 조합을 연결한다면 교착상태가 발생해 더이상 진행할 수 없어진다.

문제와 정답에 중복이 없다면 교착이 발생하지 않지만 구구단의 특성상 중복을 제거할수는 없다.
ex) 6x4, 4x6, 8x3, 3x8 = 24

해결

Queue에서 문제를 생성해서 List로 이동해 보여지는 방식을 떠올렸다.
문제Queue, 정답Queue / 문제List, 정답List 두 종류씩 만든다.

알고리즘

문제List 채우기

  1. 문제List 빈 칸에 문제Queue의 문제를 채운다. (문제Q -> 문제L)
  2. 빈 칸으로 이동시킬 문제가 없다면 새로운 문제를 생성하고, 정답을 정답Queue 랜덤 위치에 추가한다.
    (문제L : 문제 생성 / 정답Q : 정답 생성)

정답List 채우기

  1. 정답List 빈 칸에 정답Queue의 정답을 채운다. (정답Q -> 정답L)
  2. 빈 칸으로 이동시킬 정답이 없다면 새로운 문제를 생성하고, 문제는 문제Queue 랜덤 위치에 추가한다.
    (정답L : 정답 생성 / 문제Q : 문제 생성)

-> 문제List, 정답List가 모두 채워졌고, List들을 화면에 보여준다.

게임을 진행하며 반복한다.

설명

먼저 문제List를 모두 채우고, 조합이 생성될 때 정답Queue를 랜덤하게 채운다.
그 다음 정답List를 모두 채우고 마찬가지로 조합이 생성될 때 문제Queue를 랜덤하게 채운다.

  • 초기 상태

  1. 문제 이동

  2. 문제 채우기

  3. 정답 이동

  4. 정답 채우기

코드

export const queueAlgorithm = (
  questQueue: QuestArray[],
  questList: QuestArray[]
): [QuestArray[], QuestArray[]] => {
  // 큐와 리스트를 분할해 사용함
  const QQueue = [...questQueue[0]];
  const AQueue = [...questQueue[1]];
  const QList = [...questList[0]];
  const AList = [...questList[1]];

  // 문제_리스트의 빈칸을 모두 채운다.
  QList.forEach((Q, i) => {
    if (Q === null && QQueue[i] === null) {
      // 문제가 비어있고 문제_큐의 해당 칸이 비어있다면 - 문제를 생성한다.
      const [newQuest, newAnswer] = questGenerator();
      // 문제의 정답을 정답_큐의 랜덤 위치에 추가한다.
      insertRandom(AQueue, newAnswer);
      QList[i] = newQuest;
    } else if (Q === null && QQueue[i] !== null) {
      // 문제가 비어있고 문제_큐의 해당 칸이 존제한다면 - 문제를 채운다.
      const temp = QQueue[i];
      QQueue[i] = null;
      QList[i] = temp;
    }
  });

  // 정답_리스트의 빈칸을 모두 채운다.
  AList.forEach((A, i) => {
    if (A === null && AQueue[i] === null) {
      // 정답이 비어있고 정답_큐의 해당 칸이 비어있다면 - 문제를 생성한다.
      const [newQuest, newAnswer] = questGenerator();
      // 문제를 문제_큐의 랜덤 위치에 추가한다.
      insertRandom(QQueue, newQuest);
      AList[i] = newAnswer;
    } else if (A === null && AQueue[i] !== null) {
      // 정답이 비어있고 정답_큐의 해당 칸이 존제한다면 - 정답을 채운다.
      const temp = AQueue[i];
      AQueue[i] = null;
      AList[i] = temp;
    }
  });

  // 큐와 리스트 다시 병합해서 반환함
  const newQueue = [QQueue, AQueue];
  const newList = [QList, AList];
  return [newQueue, newList];
};

결론

알고리즘을 만들 때는 개발을 편하게 하기 위해서 노트에 그림을 그려가며 흐름을 정해놔야겠다.
그래도 문제를 빨리 발견해서 바로 해결할 수 있었다.

문제가 생기고 막힐 때는 잠시 쉬어가며, 어쩌다 이 지경이 되었는지 복기해보자.
일단 밥을 먹다보면 해결 방법이 떠오를 것이다.

목차