Skip to content

제안서

Jump to bottom
Seunghwan Hong edited this page Nov 9, 2018 · 50 revisions

제안서

1. 개요

요소명 내용
프로젝트명 Hidato Puzzle Generator & Solver
팀명 ALGOLINGO & DOPAMINE
문서 제목 제안서
팀원 이성재, 최찬경, 홍승환, 김상민, 박병훈, 서준교
지도교수 최준수

2. 프로젝트의 목표

2.1. 목표

이 프로젝트의 목표는 “히다토 퍼즐(Hidato Puzzle)”을 이해, 분석하여 문제를 직접 설계하고 이를 구현할 수 있는 최적의 알고리즘을 찾는 방법에 대해서 학습하는 것이다. 올바른 해결책이 제시될 수 있도록 문제를 분석 및 검증하여 설계하고, 문제 해결 시 최적의 알고리즘이 무엇인지 정의하고 가장 효율적인 알고리즘을 통해 프로그래밍하여 결과물을 도출한다. 이 프로젝트를 통해 문제 분석 능력 및 알고리즘 구현 능력을 향상시킨다.

2.2. 프로젝트 추진 배경 및 필요성

이 프로젝트는 알고리즘 구현 능력의 향상과 팀 단위의 협업 프로젝트를 완성하면서 역할 분배와 개인 개발 능력을 증진시킬 목적으로 진행하게 되었다.
이 프로젝트의 필요성은 개개인이 Hidato Puzzle 프로그램의 알고리즘을 구현하면서 recursive call과 기본 자료구조 DFS의 응용 능력을 향상시키는 것에 있다.

2.3. 기대 효과 및 활용 방안

이 프로젝트를 통해 얻을 수 있는 가장 큰 가치는 6명 팀원의 알고리즘적 사고 및 구현 능력의 향상이다. 수업을 통해 배워온 Recursive, DFS 등의 알고리즘 문제해결 전략 뿐만 아니라 Stack, Queue 등의 다양한 자료구조를 알고리즘 구현에 접목함으로써 실질적인 문제해결 능력을 배양할 수 있다. 팀원들이 힘을 합쳐 구현해낸 알고리즘은 Github 를 통해 누구나 사용해볼 수 있는 Open Source로 공개됨으로써 세계의 다양한 사람들이 공유하고, 발전시켜 나갈 수 있게 된다. 이를 통해 Hidato Puzzle 의 해결 알고리즘이 다른 사람들로부터 피드백을 받으며 성장할 뿐 아니라, 유사한 성격의 다른 게임 알고리즘들을 개발하는데 초석이 될 수 있을것으로 보인다.

3. 시스템 기능 및 구조

히다토 퍼즐은 실제로 2차원 배열의 형태를 갖는다. 다만, 본 프로젝트에서는 데이터 접근의 용이성을 위하여 1차원 배열로 저장하여 사용한다. 본 제안서에는 Generator와 Solver의 두 가지 클래스로 나누어 그 설계를 설명한다.

Generator 클래스

Generator 클래스는 다음과 같은 멤버 변수들을 포함한다.

  • int width, height, size, realSize, startIndex;
    • 순서대로 가로 길이, 세로 길이, 전체 칸 수, 실제 데이터가 존재하는 칸 수(-1 칸을 제외한 칸 수), 시작 Index를 의미한다.
  • vector<int> nextData;
    • 현재 위치의 이웃 8칸 중 하나를 무작위로 뽑은 Index를 집어넣은 배열

Generator 클래스는 다음과 같은 멤버 함수들을 포함한다.

  • randomize()
    • 주어진 맵 데이터를 전체적으로 순행하면서 현재 위치에서 getNeighbor() 함수를 통해 받아온 이웃 타일의 Index 값을 nextData에 넣어주는 함수이다. startIndex에 무작위로 위치 값을 하나 넣는다.
  • getNeighbor(<Index>)
    • 입력으로 받은 Index 값의 이웃 Index 값들 중 무작위로 하나를 뽑아서 반환하는 함수이다.
  • extract(<빈 맵 데이터>)
    • nextData안의 값을 Index로 사용하여 startIndex부터 시작해서 빈 맵 배열에 순차적으로 숫자를 부여한다. 만약 다음 위치에 이미 숫자가 있다면 이미 방문한 타일을 다시 방문한 것이므로 종료하고 현재까지 채워진 숫자의 개수를 반환한다. 서로 겹치지 않게 맵에 숫자를 순차적으로 배치하는 역할을 하는 함수라고 할 수 있다.
  • blankCount()
    • 맵에 빈 칸이 몇 개인지를 세어 반환하는 함수이다. 상술한 extract() 함수를 사용하여 구한다.
  • moveRandom()
    • 무작위 위치에서 현재 nextData에 저장된 타일과 다른 무작위 이웃 타일을 선택하는 함수이다. 원래 있던 Index를 떠나 다른 Index로 접근하기 위하여 실행된다. 혹여 잘못 이동하였을 때 돌아갈 수 있도록 nextData 값은 별도로 저장한다.
  • undo()
    • 위의 moveRandom() 함수에서 따로 저장해둔 nextData의 원래 값으로 다시 되돌아가기 위한 함수이다.
  • getRandomIndex()
    • 맵에서 무작위 위치를 뽑는 함수이다. 단, 빈 칸(-1이 들어있는 타일)은 뽑지 않는다.
  • simulate(<반복 횟수>)
    • 실제 히다토 퍼즐을 생성하는 핵심적인 역할을 하는 함수이다. randomize() 함수로 만들어진 nextData의 값을 조금씩 변경하면서 남은 빈 타일의 수를 줄이는 과정을 반복한다. 빈 타일이 모두 채워지면 완성한 것으로 판단한다.
  • generate(<맵 데이터>, <가로 길이>, <세로 길이>, <뚫릴 구멍의 개수>)
    • Generator 클래스를 이용해 생성된 히다토 퍼즐 데이터를 주어진 인자를 통해 계산하여 반환 하는 함수이다.

Solver 클래스

Solver 클래스는 다음과 같은 멤버 변수들을 포함한다.

  • int width, height, size, realSize, startIndex;
    • 순서대로 가로 길이, 세로 길이, 전체 칸 수, 실제 데이터가 존재하는 칸 수(-1 칸을 제외한 칸 수), 시작 Index를 의미한다.
  • vector<int> nextData;
    • 현재 위치의 이웃 8칸 중 하나를 무작위로 뽑은 Index를 집어넣은 배열

Solver 클래스는 다음과 같은 멤버 함수들을 포함한다.

  • solve(<맵 데이터>)

    • 맵 데이터를 받아서 solveCheck() 함수를 이용하여 실질적으로 퍼즐을 해결하는 함수이다.

  • findStart(<가로>, <세로>)

    • 시작점을 찾는 함수이다. 입력 배열에서 value 값이 1인 곳을 찾고 해당하는 좌표를 반환한다.

  • solveCheck()

    • findStart() 함수를 이용하여 시작점의 좌표를 확인 후 search() 함수를 이용하여 시작점으로부터 그 다음 검색을 시작하는 함수이다. 만약 시작점을 찾을 수 없다면 프로그램을 종료한다.

  • search()

    • 시작점에서부터 다음 단계의 숫자의 위치를 검색하여 이동하는 함수이다. getNeighbors() 함수를 통해 반환 받은 인덱스에 다음 단계의 숫자를 저장한다. recursive를 이용하여 구현하며 최종 목표 타겟 값을 발견할 때까지 반복한다.

  • getNeighbors()

    • 입력으로 받은 위치에서 이웃된 인덱스의 값을 얻는 함수이다. 자기 자신의 인덱스에서 -1을 제외한 0이 포함된 칸으로 갈 수 있는지 없는지를 체크하고 해당 좌표를 반환한다.

4. Risk Management Plan

알고리즘 프로젝트를 다수의 인원이 함께 참여하여 분담하므로 여러가지 문제가 발생할 수 있다. 예를 들면, 각 팀의 코드 인터페이스가 맞지 않아서 어느 한 쪽이 코드를 수정해야 하거나 알고리즘 분석 및 설계에 어려움이 있어 작업의 진전 속도가 느려지는 등이다. 이러한 문제의 해결을 위해서는 코드와 이를 뒷받침하는 문서들이 상시 공유되어 상호 간에 지속적으로 코드 리뷰를 주고 받아야 하며, 적절한 토론이 이루어질 수 있는 플랫폼이 존재하여야 한다.

우리 팀은 이 문제를 해결하기 위하여 Github를 사용한다. Github는 Git 프로젝트를 호스팅하는 서비스로써, 개발 과정에 도움이 되는 여러가지 기능들을 포함하고 있다. 문제를 발의하고 토론하기 위한 기능인 Issue, 서로의 코드를 비교하며 리뷰하고 합쳐나가는 과정을 지원하는 기능인 Pull Request, 각자의 작업을 정리하고 현재 진행 상황을 공유하기 위한 기능인 Project, 분석과 설계 및 회의록 등을 생성하고 유지보수할 수 있는 기능인 Wiki 등 다양한 개발자 편의 기능들이 존재한다.

모든 팀원들의 코드는 Github Repository에서 관리되며, 논의 사항, 프로젝트 진척 사항 관리 및 제반 문서 관리 또한 각각 해당 Repository의 부대 기능들을 활용하여 진행한다. 해당 Repository는 https://github.com/harrydrippin/HidatoGeneratorSolver 에서 확인할 수 있으며, MIT License로 배포된다.

5. 프로젝트 팀 구성 및 역할 분담

Generator Team: DOPAMINE

이름 역할
이성재 프로젝트 진행 사항 관리 및 제반 문서 작성
최찬경 Generator 알고리즘 설계 및 구현
홍승환 프로젝트 구조 설계 및 Risk Management

Solver Team: ALGOLINGO

이름 역할
김상민 프로젝트 진행 사항 관리 및 코드 분석
박병훈 Solver 알고리즘 설계 및 구현
서준교 프로젝트 구조 설계 및 분석

6. 개발 일정

alt text

아래 링크에서도 확인 가능합니다.
https://infogram.com/algorithm_prj-1h0r6rgpzd832ek?live

제안서 작성 : 10월 25일 - 11월 11일
프로그램 디자인 : 11월 1일 - 11월 15일
Risk Management : 11월 1일 - 12월 14일
Generator 제작 : 11월 11일 - 11월 30일
Solver 제작 : 11월 11일 - 11월 30일
Verifier 제작 : 11월 23일 - 12월 7일
코드 Merge 및 점검 : 11월 18일 - 12월 7일
테스트 및 디버깅 : 11월 18일 - 12월 14일
최종 보고서 작성 : 12월 7일 - 12월 21일

7. 참고 문헌

Clone this wiki locally