지뢰찾기 알고리즘 구현

한창 취업을 위해 이력서를 제출하고 있는데, 사전과제로 지뢰찾기를 구현하라는 과제를 받게되어 

지뢰찾기에 대해서 고민해보는 시간을 가지게 되었다. 

지뢰찾기를 제대로 해본적이 없어서 지뢰찾기를 어떻게 하는지 부터 찾아보게 되었다.

아무대나 빈 네모를 클릭 했을때 숫자가 나오는 것은 그 해당 숫자를 기준으로 

ex 1 ) 1의 주변 (자신을 제외한 8칸)에 지뢰가 1개 있음을 표시

	1
		*

ex 2 ) 3의 주변 (자신을 제외한 8칸)에 지뢰가 3개 있음을 표시

	*	*
	3
*

    

위와 같은 규칙을 가지고 있음을 알 수 있었다.

그렇다 이는 이중 배열을 써야하고 만약 [2,2]의 위치에 숫자 3이 있다고 가정한다면

지뢰는 자기자신( [2,2] ) 를 제외한 배열주소에 어딘가에 지뢰가 3개가 있음을 알 수 있는 것이다.

[1 , 1], [1 , 2], [1 , 3]

[2 , 1],             [2 , 3]

[3 , 1], [3 , 2], [3 , 3]

그럼 아래와 같은 공식을 세워볼 수 있다.

private int getMineNumber(int row, int col){
    row-1   , col-1
    row-1   , col
    row-1   , col+1
    row     , col-1
    row     , col+1
    row+1   , col-1
    row+1   , col
    row+1   , col+1
}

지뢰를 찾을 수 있는 경우의 수는 자기 자신의 배열 주소값을 제외한 총 8가지 방법이 있다.

우리는 여기서 예외상황을 두 가지 생각해볼 수 있다.

위의 경우의 수 중에, 배열의 값보다 크거나 작은 경우 예를들어 [0, 0]에 숫자 1이 있다면?

[-1 , -1], [-1 , 0], [-1 , 1]

[0 , -1], [0 , 0], [0 , 1]

[1 , -1], [1 , 0], [1, 1]

위와 같은 상황이 될 것이다. 그렇다 [-1 , -1], [-1 , 0], [-1 , 1], [0 , -1], [1 , -1] 는 배열의 주소값을 벗어난다 따라서 이를 막아줘야 한다.

private boolean isExistMine(int row, int col){
    // ArrayIndexOutOfBoundsException 예방
    if(row < 0 || row >= ROW || col < 0 || col >= COL){
        return false;
    }
}

위와 같이 지뢰의 범위를 벗어나는 경우는 조건문을 걸어 제외 시켜주었다.

큰 핵심 코드는 위의 두개라고 생각 한다.

전체 소스코드는 다음과 같다.

import java.util.Random;

/**
 * Created by developerkhy@gmail.com on 2017. 6. 15.
 * Blog      : http://soulduse.tistory.com
 * Github    : http://github.com/soulduse
 */
public class MineSweeper {

    private static final int ROW        = 10;
    private static final int COL        = 10;
    private static final int MINE_CNT   = 10;
    private static final String MINE    = " * ";
    private static final String NONE    = " x ";
    private String mineArr[][]          = null;

    public static void main(String[] args) {

        MineSweeper mineCraft = new MineSweeper();

        mineCraft.setInit();

        mineCraft.setMine(MINE_CNT);

        mineCraft.printMine();
    }

    // 생성자
    public MineSweeper(){
        mineArr = new String[ROW][COL];
    }

    // 초기화 데이터 주입
    private void setInit(){
        for(int i=0; i<ROW; i++){
            for (int j=0; j<COL; j++){
                mineArr[i][j] = NONE;
            }
        }
    }

    // 랜덤 값으로 지뢰 주입
    private void setMine(int mineCnt){
        Random ran = new Random();

        while (mineCnt-- > 0){
            int row = ran.nextInt(ROW);
            int col = ran.nextInt(COL);

            // 랜덤한 배열 주소에 이미 지뢰가 있는 경우, 루프를 한번더 돌려서 랜덤위치 재생성
            if(mineArr[row][col].equals(MINE)){
                mineCnt++;
            }
            // 값이 비어 있는 경우 지뢰를 추가한다
            if(mineArr[row][col].equals(NONE)){
                mineArr[row][col] = MINE;
            }
        }
    }

    // 지뢰 존재여부 판단
    private boolean isExistMine(int row, int col){
        // ArrayIndexOutOfBoundsException 예방
        if(row < 0 || row >= ROW || col < 0 || col >= COL){
            return false;
        }

        return mineArr[row][col].equals(MINE);
    }

    // 해당 배열 기준 자기 자신을 제외한 8칸에서 지뢰를 찾은 후 카운팅 한다.
    private int getMineNumber(int row, int col){
        int mineCnt = 0;
        if(isExistMine(row-1, col-1))mineCnt++;
        if(isExistMine(row-1, col))mineCnt++;
        if(isExistMine(row-1, col+1))mineCnt++;
        if(isExistMine(row, col-1))mineCnt++;
        if(isExistMine(row, col+1))mineCnt++;
        if(isExistMine(row+1, col-1))mineCnt++;
        if(isExistMine(row+1, col))mineCnt++;
        if(isExistMine(row+1, col+1))mineCnt++;

        return mineCnt;
    }

    // 지뢰 근처에 지뢰 개수 숫자 주입
    private void setNumber(int row, int col){
        if(mineArr[row][col].equals(NONE) && getMineNumber(row,col)!=0){
            mineArr[row][col] = " "+getMineNumber(row,col)+" ";
        }
    }

    // 지뢰찾기 배열 출력
    private void printMine(){
        for(int i=0; i<ROW; i++){
            for (int j=0; j<COL; j++){
                setNumber(i, j);
                System.out.print(mineArr[i][j]);
            }
            System.out.println();
        }
    }
}