Vite 지뢰찾기 (ViteMinesweeper)
프리뷰
개요
- React와 너비 우선 탐색 알고리즘을 활용하여 만든 Microsoft Minesweeper 스타일 지뢰찾기.
- 개인 프로젝트
- 구현 내용 요약
- 프로젝트 세팅, 최소 구현 조건 설정, 기능 구현, 테스트, 배포, 문서 및 업데이트 로그 작성, 유지보수를 담당함.
- 지뢰찾기 게임, 재방문 후 이어서 하기 등등 각종 기능 구현.
- Vite + Yarn Berry로 프로젝트를 세팅하여 Create React App 대비 로딩 시간 30초 → 5초로 감소, 설치 속도가 5배 빨라짐.
- 빈 타일 클릭 후 8방향 주변의 또다른 빈 타일을 탐색하기 위해 활용한 BFS 알고리즘에 쓰인 큐를 Array.prototype.shift() 기반에서 링크드 리스트 기반으로 변경하여, 큐의 pop 시간 복잡도를 O(n)에서 O(1)로 개선함.
방문하기
이 프로젝트를 만든 이유
Microsoft Minesweeper의 규격을 따르는 지뢰찾기를 다운로드 없이 플레이하고 싶어 제작을 시작했습니다. Windows 8 이후로 Microsoft Minesweeper는 기본 게임에서 제외되었습니다. 물론 Microsoft 공식 지뢰찾기 게임을 다운받아 플레이할 수 있으나, 불필요하게 화려한 그래픽과 광고 등등의 문제점을 안고 있습니다. Google이 제공하는 지뢰찾기 또한, 규격(너비와 높이 등등)은 기존에 알던 Microsoft Minesweeper의 규격과 달라 아쉬움을 느꼈습니다. 이러한 이유로 Microsoft Minesweeper의 규격을 따르는 지뢰찾기를 다운로드 없이 플레이하고 싶었습니다.
플레이 방법 (Windows Chrome 기준)
- 게임의 룰은 Microsoft Windows 7까지의 기본 게임이었던 Microsoft Minesweeper의 룰을 지향하고 있습니다.
- 마우스 좌클릭으로 방문되지 않은 타일을 확인할 수 있습니다.
- 마우스 우클릭으로 방문되지 않은 타일에 지뢰가 있다고 짐작하는 `마킹`을 남길 수 있습니다.
- 마우스 양쪽 클릭으로 주변에 지뢰가 있는지 확인할 수 있습니다.
- 숫자와 주변 마킹의 개수가 일치하지 않으면 작동하지 않습니다.
- 지뢰를 건드리거나 모두 찾으면 게임이 종료됩니다.
- Reset 버튼으로 게임을 다시 시작할 수 있습니다.
- Config 버튼으로 게임의 규격을 설정할 수 있습니다. 설정 시 진행 중인 게임은 초기화됩니다.
- 게임에서 설정할 수 있는 규격의 범위입니다.
- 너비: 9 ~ 30칸
- 높이: 9 ~ 16칸
- 지뢰 개수: 10 ~ Floor(너비 * 높이 * 0.925)개
사용한 기술 스택
이 프로젝트에서 기술적으로 기뻤던 점: 지뢰찾기 구현에 쓰인 알고리즘인 BFS(너비 우선 탐색) 활용
이전까진 각종 프로젝트를 진행하면서 컴퓨터공학 지식을 활용할 수 있는 곳이 없었으나, ViteMinesweeper를 계기로 컴퓨터공학 지식 중 하나인 알고리즘 중 BFS(너비 우선 탐색)을 활용할 수 있어서 기뻤습니다. BFS는 지뢰찾기 게임에서 탐색되지 않은 어떤 타일을 눌렀을 때 또다른 숫자 타일이나 가장자리에 다다를 때까지 주변 8방향으로의 빈 타일 탐색을 수행하는 과정에 적용하였습니다.
BFS 큐의 Pop 호출 시간 복잡도 개선
앱 속도 개선 작업 이전에는, 사용자들로부터 앱의 반응이 약간 느리다는 피드백을 받았습니다. 그 원인 중 하나가, Array.prototype.shift()를 큐의 pop에 사용하고 있었다는 점이었습니다. 실제로, Array.prototype.shift()는 배열의 맨 앞 원소 제거 후 나머지 원소의 인덱스가 전부 변경되므로, 한 번 실행할 때마다 배열의 길이만큼의 연산 시간을 가집니다. 즉, 시간복잡도가 O(n)이라는 이야기이죠.
이를 개선하기 위해 시간복잡도가 O(1)인 pop 방법을 사용 해야 했는데, 그 방법이 링크드 리스트 기반의 pop을 사용하는 큐를 직접 만드는 것이었습니다. 링크드 리스트를 사용하면, 맨 앞 원소 front를 pop할 때 front만 그 뒤를 가리키게 만들고 이전에 front였던걸 반환하기만 하면 됩니다. 이렇게 Array.prototype.shift() 기반의 pop을 사용하는 큐를 직접 구현한 링크드 리스트 큐로 교체함으로써, 앱의 속도를 개선했습니다.
큐가 얼마나 잘 작동하는지 검증하는 수단으로, 백준에서 큐를 사용하는 유형의 문제 풀이에 응용했습니다. (예시 문제) 81596705호 제출은 Array.prototype.shift() 기반의 pop을 사용하고 있으며, 81596769호 제출은 링크드 리스트 기반의 pop을 사용하고 있습니다. 여기서, 링크드 리스트를 사용했을 때가 Array.prototype.shift()를 사용했을 때보다 44ms 더 빨라지는것을 알 수 있습니다.