-
Notifications
You must be signed in to change notification settings - Fork 1
최종 보고서
| 요소명 | 내용 |
|---|---|
| 프로젝트명 | Hidato Puzzle Generator & Solver |
| 팀명 | ALGOLINGO & DOPAMINE |
| 문서 제목 | 제안서 |
| 팀원 | 이성재, 최찬경, 홍승환, 김상민, 박병훈, 서준교 |
| 지도교수 | 최준수 |
이 프로젝트의 목표는 “히다토 퍼즐(Hidato Puzzle)”을 이해, 분석하여 문제를 직접 설계하고 이를 구현할 수 있는 최적의 알고리즘을 찾는 방법에 대해서 학습하는 것이다. 올바른 해결책이 제시될 수 있도록 문제를 분석 및 검증하여 설계하고, 문제 해결 시 최적의 알고리즘이 무엇인지 정의하고 가장 효율적인 알고리즘을 통해 프로그래밍하여 결과물을 도출한다. 이 프로젝트를 통해 문제 분석 능력 및 알고리즘 구현 능력을 향상시킨다.
이 프로젝트는 알고리즘 구현 능력의 향상과 팀 단위의 협업 프로젝트를 완성하면서 역할 분배와 개인 개발 능력을 증진시킬 목적으로 진행하게 되었다.
이 프로젝트의 필요성은 개개인이 Hidato Puzzle 프로그램의 알고리즘을 구현하면서 recursive call과 기본 자료구조 DFS의 응용 능력을 향상시키는 것에 있다.
이 프로젝트를 통해 얻을 수 있는 가장 큰 가치는 6명 팀원의 알고리즘적 사고 및 구현 능력의 향상이다. 수업을 통해 배워온 Recursive, DFS 등의 알고리즘 문제해결 전략 뿐만 아니라 Stack, Queue 등의 다양한 자료구조를 알고리즘 구현에 접목함으로써 실질적인 문제해결 능력을 배양할 수 있다. 팀원들이 힘을 합쳐 구현해낸 알고리즘은 Github 를 통해 누구나 사용해볼 수 있는 Open Source로 공개됨으로써 세계의 다양한 사람들이 공유하고, 발전시켜 나갈 수 있게 된다. 이를 통해 Hidato Puzzle 의 해결 알고리즘이 다른 사람들로부터 피드백을 받으며 성장할 뿐 아니라, 유사한 성격의 다른 게임 알고리즘들을 개발하는데 초석이 될 수 있을 것으로 보인다.
본 보고서에는 역할 분담에 따라 Solver와 Generator & Verifier의 두 가지 부분으로 나누어 그 설계를 설명한다.
Hidato Puzzle에서 Solver의 역할은 퍼즐에 존재하는 숫자를 대각선 및 상하좌우 방향으로 검사하여 최종 target까지 도달하게 하는 것이다. 현재 위치에서 8가지 방향으로 검사를 진행하고 올바른 경로가 아닐 시에 다시 자신을 호출한 이전 지점으로 돌아와서 다른 방향에 대한 경로 탐색이 필요하다. 따라서 Hidato Puzzle의 Solver 구현에 대해서 팀원 간 상의한 결과, DFS 알고리즘과 Backtracking 기법을 이용하여 프로그램을 구현하기로 결정하였다.
(Generator & Verifier)
< Solver Team Meeting >
11 / 8(목)
- 구체적인 프로그램 구현에 앞서 어떤 알고리즘을 사용할지 상의한다.
- 상의 결과 DFS알고리즘을 사용하기로 결정한다.
11 / 13(화)
- Solver 함수의 핵심인 solver를 현재 위치에서 갈 수 있는 8가지의 방향 중 value+1을 발견하거나 0을 발견했을 때 두가지 조건으로 구분하여 작성한다.
- 첫번째로 value+1을 발견하면 recursive를 이용하여 value+1의 값을 가진 위치에서 위와 같은 행동을 반복한다. 이 때, isCheckArr[value+1]배열에 true를 적어준다. 만약 올바른 길로 갈 수 없을 시에 다시 value 위치로 backtracking 하여 올바른 길을 재탐색하며 isCheckArr[value+1]을 false로 수정한다.
- 두번째로 0을 발견하였을 때는 이 위치에 value+1을 적어주고 첫번째와 동일한 작업을 수행한다. 이와 같은 작업을 반복하다가 value 값이 target과 일치한다면 최종으로 true를 반환한다. 만약 올바른 input파일이 아니였다면 false를 반환한다.
11 / 20(화)
- 프로그램의 효율성을 높이기 위해 8개의 좌표배열을 만들고 이중 for문을 단일 for 문으로 수정하고, 그에 따른 불필요한 연산을 제거하였다.
11 / 27(화) Generator가 만드는 예시를 입력 받아 올바른 결과물을 출력하는지 확인한다.
- 오류 수정 내용 : search 함수 안에 nextPoint가 max와 같은지 비교하는 조건문에서 종료조건을 max에서 max+1로 바꾸었고, isCheckArr[]의 배열 크기를 하나 늘려준다.
(Generator & Verifier)
Solver를 이용하여 Generator가 생성한 input파일을 해결하여 이를 verifier가 검사 할 수 있게 파일로 출력한다. (* 사진 : solver 실행전, solver 실행후 ) // 사진 2개 정도
(Solver)
(Generator & Verifier)
| 이름 | 역할 |
|---|---|
| 이성재 | 프로젝트 진행 사항 관리 및 제반 문서 작성 |
| 최찬경 | Generator 알고리즘 설계 및 구현 |
| 홍승환 | 프로젝트 구조 설계 및 Risk Management |
| 이름 | 역할 |
|---|---|
| 김상민 | 프로젝트 진행 사항 관리 및 코드 분석 |
| 박병훈 | Solver 알고리즘 설계 및 구현 |
| 서준교 | 프로젝트 구조 설계 및 분석 |
- 위키백과, "Hidato"