[Java 알고리즘] 지뢰찾기 알고리즘(주변 지뢰 숫자 세기)

지뢰찾기 게임을 제작한다고 가정하고, 각 사각형에 표시될 숫자를 입력하는 코드를 작성하시오.

출력 예시)

 

조건

• 사각형의 크기는 10x10 
• 지뢰의 갯수는 10개로 가정하고, 임의의 위치에 놓여있다고 하거나 직접 위치를 지정해도 무관함
• 지뢰는 “ * ” 로 표시할 것.

 

나의 풀이

class Scratch {
    
    public static void main(String[] args) {
        Scratch a = new Scratch();
        Cell[][] cells = new Cell[10][10];
        for (int i =0; i<cells.length; i++) {
            for (int j =0; j<cells[i].length; j++) {
                cells[i][j] = new Cell(0, false);
            }
        }
        cells[0][1] = new Cell(0, true);
        cells[2][2] = new Cell(0, true);
        cells[1][1] = new Cell(0, true);
        cells[1][8] = new Cell(0, true);
        cells[8][7] = new Cell(0, true);
        cells[4][6] = new Cell(0, true);
        cells[7][2] = new Cell(0, true);
        cells[5][4] = new Cell(0, true);
        cells[6][5] = new Cell(0, true);
        cells[7][1] = new Cell(0, true);

        a.print(a.solution(cells));
    }

    public Cell[][] solution(Cell[][] cells) {
        if(cells == null || cells.length == 0) return new Cell[][]{};
        for (int i =0; i<cells.length; i++) {
            for (int j = 0; j < cells[i].length; j++) {
                cells[i][j].count = getVal(cells, i, j);
            }
        }
        return cells;
    }

    int[][] dirs = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
    public int getVal(Cell[][] cells, int x, int y) {
        if(cells[x][y].isZ) return 0;
        int count = 0;
        for(int[] dir : dirs) {
            int pointX = dir[0] + x;
            int pointY = dir[1] + y;
            if(pointX >= 0 && 
               pointY >= 0 && 
               pointX < cells.length && 
               pointY < cells[0].length && 
               cells[pointX][pointY].isZ == true) {
               
                count++;
            }
        }
        return count;
    }

    public void print(Cell[][] cells) {
        for (int i =0; i<cells.length; i++) {
            for (int j =0; j<cells[i].length; j++) {
                System.out.print(String.format("%2s ", cells[i][j].isZ ? "*" : cells[i][j].count));
            }
            System.out.println();
        }
    }

}
class Cell {
    int count;
    boolean isZ;

    Cell(int count, boolean isZ) {
        this.count = count;
        this.isZ = isZ;
    }
}

일단 Cell 이라는 클래스를 만들어서 isZ 라는 인스턴스 지뢰여부 데이터와 주변 지뢰의 갯수정보를 갖고있는 count를 선언하였습니다.

기본적으로 dfs라는 깊이우선탐색 알고리즘을 공부하면서 비슷한 내용이길래 적용해보았습니다. 

 

main 메소드 부분은 대부분 지뢰를 생성하여 배열에 담는 로직입니다. 문제에서 애초에 이런 제한을 두지 않았기 때문에 Cell이라는 클래스를 생성했습니다. 만약 solution 메소드를 String[][], int[][] 로 추상적으로 파라미터로 넘겨주고 메소드를 정의해야했다면 달라졌겠죠.

 

print 메소드는 단지 출력용 메소드입니다.

 

이제 중요한 solution 메소드인데 여기는 cell[i][j]에 for문으로 한번씩 접근을 해야하고 getVal이라는 메소드를 통해 주변 데이터를 탐색합니다.

 

getVal 메소드는 dirs 라는 변수로 선언한 셀 주변 상대좌표를 통해 실질 좌표를 얻고 주변에 지뢰(*)가 있는지 판단합니다. 물론 if문을 통해서 0번째 행일 때 -1 좌표가 없는 점을 고려해 좌표가 음수인 경우를 제거해주고 grid의 length를 통해 유효성 검사를 해줍니다.

 

이렇게 getVal로 count를 반환하면 한 cell[i][j]의 count를 얻게되고 마지막까지 수행한 후 print를 통해 위의 예시처럼 출력하게 됩니다.