【Paiza】Javaで五目並べ問題を1次元配列で解く

# 【Paiza】Javaで五目並べ問題を1次元配列で解く

この記事では、PaizaのBランクレベルアップ問題集の中にある五目並べの問題を二次元配列を用いずに一次元配列のみで解く酔狂な解法を紹介したいと思います！
実際の業務では中々使うことのないようなロジックにはなりますが、「こんな考え方もあるのかぁ」と読んでもらえると幸いです！

## 目次
1. [問題の概要](#1-問題の概要)
2. [解法のアイデア](#2-解法のアイデア)
3. [コード解説](#3-コード解説)
    - [ 一次元配列に置き換える方法](#一次元配列に置き換える方法)
    - [数列の法則](#数列の法則)
    - [判定と出力](#判定と出力)
4. [まとめ](#4-まとめ)

## 1. 問題の概要

この問題は、"O"と"X"で五目並べの駒の種類を示し、入力された盤面を読み取ってどちらが勝者か、それとも引き分けかを判定するコードを書くという問題です。
通常この手の問題は二次元配列の考え方で解くのが主流ですが、敢えて一次元配列で今回は解いてみました笑

[問題文はこちら](https://paiza.jp/works/mondai/prob60/tic_tac_toe_9)


## 2. 解法のアイデア

まず、一次元配列でこの問題を解くために以下のように入力される配列を一次元に並べ替え、盤面の縦・横・斜めに関しての数列の法則を見つけることで判定の処理をするというアイディアのもとこの問題を解きました！

入力例

XXOXO
OXOXX
.OXXO
OXOO.
XXXXX

## 3. コード解説

### 一次元配列に置き換える方法

Javaにおいてリストの要素や文字列の順番を示す際1番目を0と表すため、0から始まる数列で法則を考えました。そして、入力された文字列を一次元配列に変換させ、法則に基づいて並べ替えをして勝敗を判定しました。
そのために行った処理を紹介します。

入力された情報に対してnextLine()メソッドを用いることによって1行ずつ読み取り、それを一旦ひとつのString型の文字列として連結させ、splitメソッドを用いることで改めて1次元配列のリストを作り数列の法則に則って縦・横・斜めの判定用のリストを追加で作成するという方法を取りました。
<br>
一次元配列への変換処理
```Java
        //盤面が1辺いくつかを入力
        int num = 5;
        
        Scanner sc = new Scanner(System.in);
        
        //numの2乗文字のString型の値を作成
        String o_list = "";
        for (int i = 0; i < num; i++){
            o_list += sc.next();
        }
        
        //入力された値の一次元配列のリストを作成
        String list[] = o_list.split("");
```

　元の入力された値を一次元配列に変換することができたので、次に数列の法則に従ってリストの要素を並べ替えた勝敗判定用のリストを作っていきます！


### 数列の法則

勝利の判定を行うために縦、横、斜めの数列の法則を図1と見比べながら考えていきます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3839504/8d3807d8-3266-002f-cfb8-1d37a788c455.png)


**・横の法則**
　以下のように縦の判定に関しては一辺の長さで割った商に注目して分類をすれば簡単に判別することができます。今回は5×5の盤面であるため、変数numに5を入力してあります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3839504/8350be13-f1e3-3a24-ba44-854a3b0ed038.png)

<br>
実際のコードはこちらです。
 
```Java
        //横の文字列を判別するためのリスト作成
        String[] result_s = new String[num];
        for (int i = 0; i < num; i++){
            for (int j = 0; j < num * num; j++){
                if (j / num == i && j % num == 0){
                    result_s[i] = list[j];
                } else if(j / num == i && j % num != 0){
                    result_s[i] += list[j];
                }
            }
        }

```
**・縦の法則**
　以下のように横の判定に関しては一辺の長さで割った余りに注目して分類をすれば簡単に判別することができます。今回は5×5の盤面であるため、変数numに5を入力してあります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3839504/57bf251b-51f0-8006-b088-536f2028f9c5.png)

<br>
実際のコードはこちらです。

```Java
        //縦の文字列を判別するためのリスト作成
        String[] result_v = new String[num];
        for (int i = 0; i < num; i++){
            for (int j = 0; j < num * num; j++){
                if (j % num == i && j / num == 0){
                    result_v[i] = list[j];
                }else if(j % num == i && j / num != 0){
                    result_v[i] += list[j];
                }
            }
        }

```

**・斜めの法則**
　そして少し厄介なのが斜めの分類です。しかし、以下の図を見ると面白い法則が見つかります！
 　以下の図のように今回のような5×5の盤面では右下がりの斜めは6の倍数、左下がりの斜めは4の倍数という法則が見つかりました！
　そしてこの法則は1辺の数が増えても適応され、変数numを用いて処理をすることができます！
<br>
 右下がりの斜め
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3839504/79128842-e8b1-f66e-7e29-f2ccb9c030e4.png)

<br>
左下がりの斜め

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3839504/d9131a60-e5bb-574a-1d36-c9d9ebead7f5.png)

実際のコードはこちらです。

```Java
        //斜めの文字列を判別するためのリスト作成
        String[] result_d = new String[2];
        
        //右下がりの斜め
        for (int j = 0; j < num * num; j++){
            if (j == 0){
                result_d[0] = list[j];
            }else if(j % (num + 1) == 0 && j != 0){
                result_d[0] += list[j];
            }
        }
        
        //左下がりの斜め
         for (int j = 0; j < num * num; j++){
            if (j == (num -1)){
                result_d[1] = list[j];
            }else if(j % (num -1) == 0 && j != 0 && j != (num -1) && j!= (num -1) * (num + 1) ){
                result_d[1] += list[j];
            }
        }

```

### 判定と出力
　判定についての処理は先ほど作成をした横、縦、斜めの判定用のリストの中に"OOOOO"か"XXXXX"が含まれているかどうかで処理を行うようにしました！判定の変数answerの値の初期値を引き分けを表す"D"と設定し、もし一列同じ記号で揃っている箇所を発見したらその結果に基づいて勝者を出力するようにコードを書きました。

 実際のコードはこちらです。

 ```Java
       //判別処理
       //初期値がDの変数を用意
       String answer = "D";
       
       
        //横の判別
        for (int i = 0; i < num; i++){
            if (result_s[i].equals("OOOOO")){
                answer = "O";
                break;
            }else if (result_s[i].equals("XXXXX")){
                answer = "X";
                break;
            }else{
                answer = answer;
            }
        }
        
        //縦の判別
        for (int i = 0; i < num; i++){
            if (result_v[i].equals("OOOOO")){
                answer = "O";
                break;
            }else if (result_v[i].equals("XXXXX")){
                answer = "X";
                break;
            }else{
                answer = answer;
            }
        }
        
        //斜めの判別
        for (int i = 0; i < 2; i++){
            if (result_d[i].equals("OOOOO")){
                answer = "O";
                break;
            }else if (result_d[i].equals("XXXXX")){
                answer = "X";
                break;
            }else{
                answer = answer;
            }
        }
        
        
        System.out.println(answer);

```

## 4. まとめ

　今回は二次元配列で考える問題を敢えて一次元配列で解くという酔狂な真似をしたのですが、数列の面白さを感じることができたのでQiitaで共有しようと思い投稿をしました！
 　私自身まだまだプログラミング初学者ではあるので「もっとこうしたら良いよ！」などの意見があればどしどし反応していただけると幸いです！
　今後も業務や趣味のプログラミングの中で見つけた面白いアルゴリズムについて紹介していこうと思うので宜しくお願いします！