【Paiza】島探し JavaScript編 解いてみただけの記事


書類仕事に飽きた！ので腕試し。

## 問題

こんな企画をやってたので遊ぶ。  

https://qiita.com/official-events/9ab96aa95d62fe3cbdd7

こういうゲームアルゴリズム大好き...なので島探しをチョイス。  
やるならSランクよなぁ！

https://paiza.jp/works/mondai/s_rank_skillcheck_sample/search-island


## 作戦その1 - 愚直にチェック

こういうのは図で書いたら分かりやすい！  
地図用の配列と、島フラグ用の配列を用意する。

1. 左上から右下に向かって順番にマスを検査して、島だったら島登録をはじめる。  
2. 上と左要素を確認して、島だったらその島と同じ島として登録する。
3. それ以外は新規の島として扱う。

```javascript
var lines = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');

// map を作る
var row = 0
var col = 0
var map = []
for (const key in lines) {
    const cells = lines[key].split(' ').map(cell => parseInt(cell))
    
    if (key == 0) {
        [col, row] = cells
    } else if (key <= row) {
        map.push(cells)
    }
}
console.log(map)

// 島情報の格納先を作る
var island = [...Array(row)].map(_ => Array(col).fill(0))

// 左上からカーソルを進めて、島をカウントしていく
var islandNo = 0
for (let r = 0; r < row; r++) {
    for (let c = 0; c < col; c++) {
        // セルが島であれば判定する
        if (map[r][c] && !island[r][c]) {
            if (r-1 >= 0 && island[r-1][c]) {
                // 上要素を確認し、島であれば連結させる
                island[r][c] = island[r-1][c]
            } else if (c-1 >= 0 && island[r][c-1]) {
                // 左要素を確認し、島であれば連結させる
                island[r][c] = island[r][c-1]
            } else {
                // それ以外は新規の島とする
                island[r][c] = ++islandNo
            }
        }
        console.log('---', r, c)
        console.log(island)
    }
}

console.log(map)
console.log(island)
```

![drawio (11).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3833190/f7308081-cb6d-6d95-ef9d-73c226a0a2d4.png)

だめじゃん！
左に伸びた半島が検出できない...





## 作戦その2 - 島を先に探す

ぐぬぬぬ...  
こねくり回したが、島を見つけたら先に、その島を探索し終えないといけないかもしれない。
やってみる。

1. 左上から右下に向かって順番にマスを検査して、島だったら島登録をはじめる。  
2. 四方を確認して、島だったら同一の島とする。
3. その際に発見した島についても、四方を確認して 2. を繰り返す。

※ 2.3. ループは簡単にするために、スタックを用いた！

![drawio (12).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3833190/191e0c5d-9da2-839b-d5df-03c80e5349be.png)

```javascript
var lines = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');

// map を作る
var row = 0
var col = 0
var map = []
for (const key in lines) {
    const cells = lines[key].split(' ').map(cell => parseInt(cell))
    
    if (key == 0) {
        [col, row] = cells
    } else if (key <= row) {
        map.push(cells)
    }
}
console.log(map)

// 島情報の格納先を作る
var island = [...Array(row)].map(_ => Array(col).fill(0))

// 左上からカーソルを進めて、島をカウントしていく
var islandNo = 0
for (let r = 0; r < row; r++) {
    for (let c = 0; c < col; c++) {
        // セルが未発見の島であれば判定を開始する
        if (map[r][c] && !island[r][c]) {
            // 自身を新規の島にする
            island[r][c] = ++islandNo
            
            // 4方向を確認して新規の島を探す
            var stack = [[r, c]]
            while (stack.length > 0) {
                console.log('sub')
                console.log(stack)
                
                const [sr, sc] = stack.shift()
                if (sr-1 >= 0 && map[sr-1][sc] && !island[sr-1][sc]) {
                    // 上方向に島があったら染めてpush
                    island[sr-1][sc] = islandNo
                    stack.push([sr-1, sc])
                }
                if (sc-1 >= 0 && map[sr][sc-1] && !island[sr][sc-1]) {
                    console.log('left')
                    // 左方向に島があったら染めてpush
                    island[sr][sc-1] = islandNo
                    stack.push([sr, sc-1])
                }
                if (sr+1 < row && map[sr+1][sc] && !island[sr+1][sc]) {
                    // 下方向に島があったら染めてpush
                    island[sr+1][sc] = islandNo
                    stack.push([sr+1, sc])
                }
                if (sc+1 < col && map[sr][sc+1] && !island[sr][sc+1]) {
                    // 右方向に島があったら染めてpush
                    island[sr][sc+1] = islandNo
                    stack.push([sr, sc+1])
                }
            }
            console.log('end sub')
        }
        console.log('---', r, c)
        console.log(island)
    }
}

console.log(map)
console.log(island)
```

できたじゃん！
なるほどね～先に埋めないといけないのか





### 作戦その3 - 最適化

作戦2のやり方なら、見つけた島を地図から消していけば、配列一個でも実現できそう。  
探索先を減らせないか考えたが、蛇みたいな島が検出できなくなるので無理そう。。

```javascript
var lines = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');

// map を作る
var row = 0
var col = 0
var map = []
for (const key in lines) {
    const cells = lines[key].split(' ').map(cell => parseInt(cell))
    
    if (key == 0) {
        [col, row] = cells
    } else if (key <= row) {
        map.push(cells)
    }
}

// 左上からカーソルを進めて、島をカウントしていく
var islandNo = 0
for (let r = 0; r < row; r++) {
    for (let c = 0; c < col; c++) {
        // セルが島であれば判定を開始する
        if (map[r][c]) {
            // 自身を新規の島にする
            map[r][c] = 0
            islandNo ++
            
            // 4方向を確認して新規の島を探す
            var stack = [[r, c]]
            while (stack.length > 0) {
                const [sr, sc] = stack.shift()
                if (sr-1 >= 0 && map[sr-1][sc]) {
                    // 上方向に島があったら染めて再チェック
                    map[sr-1][sc] = 0
                    stack.push([sr-1, sc])
                }
                if (sc-1 >= 0 && map[sr][sc-1]) {
                    // 左方向に島があったら染めて再チェック
                    map[sr][sc-1] = 0
                    stack.push([sr, sc-1])
                }
                if (sr+1 < row && map[sr+1][sc]) {
                    // 下方向に島があったら染めて再チェック
                    map[sr+1][sc] = 0
                    stack.push([sr+1, sc])
                }
                if (sc+1 < col && map[sr][sc+1]) {
                    // 右方向に島があったら染めて再チェック
                    map[sr][sc+1] = 0
                    stack.push([sr, sc+1])
                }
            }
        }
    }
}

console.log(islandNo)
```


### まとめ

これ以上は読みにくくなるから、私の感性ではこれで完成。

たまにはアルゴリズムの特訓良いよね。
でも実務ではあまり役に立たない悲しさ。。。