지뢰찾기 - 2

지뢰 찾기 게임을 만들면서 알고리즘이 무엇이 필요할까 싶지만 몇 가지 고민은 필요하다.

 

( 1 )
처음으로 "지뢰를 임의로 숨겨둔다" 의 알고리즘이 필요하다.

이는 임의 를 구성하는 여러 방법 중에 하나를 사용하면 된다.

 

주어진 블록은 가로 & 세로로 구성되어 하나의 Index 로 표현할 수 있다 ( 1 차원 Array )

지뢰 갯수 M 을 입력 받았을 때 배열 A 에 M 개 만큼의 블록에 지뢰 상태를 부여하고, 배열 A 를 섞었다.

for (var i = block_side_num ** 2 - 1; i > 0; i--) {
            var j = Math.floor(Math.random() * (i + 1));
            [blocks[i], blocks[j]] = [blocks[j], blocks[i]];
        }

( N^2 의 기대 횟수에서 구성 요소의 위치를 바꾼다 )

 

( 2 )

오픈한 블록의 인접 블록이 지뢰가 아닌 경우 같이 열어 주는 효과가 필요하다.

이는 선택된 블록이 i 일 때, 상/하/좌/우의 인접한 블록을 접근하고 다시 주변의 블록을 찾아가는 BFS 로 방문한 블록을 기록하면 된다.

i 에서 시작 // i 의 [ x, y ] 2 차원 index 를 얻음
answer = []
[ x-1, y ], [ x+1, y ], [ x, y-1 ], [ x, y+1] 의 block 의 index 를 얻음
조건에 만족하는 index 만 answer 에 기록함 // answer 에 기록이 없거나 지뢰가 아닌 블록
// 한 방향으로 확장되어 visited 는 필요하지 않음