지뢰찾기 게임을 구현할 때 재귀 호출에 대한 리팩토링

의견 추가하기↓ / SLiPP 최신의견↓ / 페북 최신의견↓
자바지기 2013-12-04 09:46

요즘 학생들과 지뢰찾기 게임을 구현하고 있다. 구현하고 있는 소스 코드는 https://github.com/javajigi/minesweeper에 있다.

지뢰찾기 게임을 구현해 보면 특정 square(지뢰찾기에서 사각형 한칸을 square라고 했다.)을 여는 경우 해당 square가 이웃하고 있는 지뢰 숫자가 아무 것도 없는 0이면 주변 8방향에 있는 square를 자동으로 열어야 한다. 자동으로 열리는 square가 다시 0이면 해당 square 주변 8방향의 square 또한 자동으로 열려야 한다. 이 부분을 구현하는 가장 좋은 방법은 재귀 호출을 통해 해결하는 것이다.

이 부분의 구현 코드를 리팩토링한다면 어떻게 하면 좋을까? 현재 자바 소스 코드의 구조는 다음과 같다. Grid(지뢰찾기 게임 판) - Row(지뢰 찾기 게임의 열을 담당) - Square와 같은 구조로 되어 있다.

public class Grid {


    private Row rows[];


    [...]


    public int openSquare(int row, int col) throws GameoverException {
        Square square = getSquare(row, col);
        square.setOpen();
        if (!square.isMine()) {
            int startRow = (row - 1 < 0) ? row : row - 1;
            int endRow = (row + 1 < getRow()) ? row + 1 : row;


            if (square.getNumOfNearMines() == 0){
                for (int i = startRow; i <= endRow; i++) {
                    Row rowOfGrid = rows[i];
                    rowOfGrid.openSquare(i, col, this);
                }
            }
            
            return square.getNumOfNearMines();
        }
        throw new GameoverException();
    }
}

이 상태에서 재귀 호출을 하려면 직접 할 수 없기 때문에 Row에 Grid를 전달해 재귀 호출을 하고 있다.

public class Row {
    private Square[] squares;


    [...]


    public void openSquare(int row, int col, Grid grid) throws GameoverException {
        int startCol = (col-1 < 0)? col : col-1;
        int endCol = (col+1 < getCol())? col+1 : col;
        
        for (int j = startCol; j <= endCol; j++) {
            if (squares[j].isOpen()) continue;


            squares[j].setOpen();
            if (squares[j].getNumOfNearMines() == 0)
                grid.openSquare(row, j);
        }      
    }
}

2차원 배열을 Grid가 가지고 있는 상태라면 Grid 내에서 재귀 호출을 통해 해결하면 되지만 2차원 배열을 사용할 경우 무한 반복되는 2중 for문이 짜증나 위와 같이 Row 클래스를 만들어 2중 for문을 제거하도록 구현했다. 그랬더니 위와 같은 형태의 재귀 호출이 생겼다.

이 같은 상황이라면 어떻게 리팩토링하겠는가? 그냥 Grid에서 2차원 배열을 사용하는 것이 좋겠는가? 아직 우리도 리팩토링을 시작한 단계는 아니다. 다음 주에 구현할 과제이다. 여러분이 이 같은 상황에서 리팩토링을 한다면 어떻게 하겠는가?

0개의 의견 from FB

3개의 의견 from SLiPP

jhindhal.jhang 2013-12-04 11:48

일단 오래 생각해보지 않았는데 객체를 좀 다르게 생각해야 하지 않을까? Row가 있을 필요가 있을까? 한다.

그냥 Square 객체가 mine/empty 속성과, rowIdx, colIdx를 가지고 List getNeighbors(){} 로 이웃 square들을 return하게 하고 재귀로 돌면 되지 않을까? 재귀 안에서 로직은 neighbor.isMine() 일때까지 재귀를 돌면 될듯, 거기에 이웃을 호출한 Square를 parent로 두고 parent일때는 재귀호출을 skip하고 모든 이웃이 isEmpty()이면 openSquare()를 하는 방식이 어떨까?

sudo code해보면

class Square {
boolean mine;
int rowIdx;
int colIdx;
List<Square> neighbors; // 이건 초기 설정을 해줘도 되고 row, col로 계산해서 return해도 될듯
int neighborsCount;
get...
set...
public boolean isMine() return mine;
// 자신을 호출한 부모를 제외한 이웃이 모두 지뢰가 아닌지 확인
public isAllNeighborsEmpty(parent) {
boolean isAllNeighborsEmtpy = ture;
  for(Square neighbor : neighbors) {
    if(!parent.equals(neighbors.get(i)) isAllNeighborsEmtpy = neighbors.get(i).isEmpty();
  }
}
//순차적으로 이웃을 return할수있게(벽일때도 고려해야함)
public Square getNextNeighbor() {
return neighbors.get(index); 
}


equals()...


}


public openSquare(Square square, Square parent) {
if(square.isMine()) throws new GameOverException();
if(square.isAllNeighborsEmtpy(parent)) {
  square.open();
  if(square.isNextNeighbor())
    openSuare(square.getNextNeighbor(), square);
  else return;
}
}

대략 위와같은 코드가 나오지 않을까? 걍 생각나는데로 슈도코드를 만들어서 버그는 많을듯....

enshahar 2013-12-04 13:09

-아예 객체 타입을 3단계로 나누는 방법도 있을 것 같습니다. NxM의 Square type의 배열을 사용하되, Square를 상속해서...

일반 로직은 Square안에 넣어두고..

1) 마인객체 : OnClick => Boom!

2) 숫자객체: OnClick => Reveal Number

3) 빈칸 객체: 주변 빈칸객체를 링크로 가지고 있고, OnClick => 주변 빈 칸 객체 중 open되지 않은 객체에 대해 오픈하는 함수 재귀호출

좀 더 머리(?)를 쓴다면, 3)에서 사실은 모든 빈 칸들은 한꺼번에 열려야 하는 인접칸들의 집합(원소갯수는 1개 이상)에 속해있을테니, 빈칸 객체의 경우 해당 집합(이건 어떤 종류이건 iterable하면 되죠)으로의 링크를 걸어두면, 재귀호출 없이 해당 iterable에 대해 open하는것만으로도 해결 가능.

--;; 코딩은 시간이 없어서 나중에..

아라한사_일반 2020-08-02 10:05

https://adunhansa.tistory.com/325

오랜 글이어서 적을까 말까 고민했다가 후대(?)에 같은 고민으로 찾아올 친구가 있을 수도 있다고 생각하여 적어보자면

이동하는 방식에 대하여 전략객체화를 시킨 뒤, 0 의 전파같은 경우는 위의 글에서 Block 객체 안에 다음과 같은 메서드를 만들어주면 될 것같다고 생각합니다.

public Block 이벤트전파(MovingStrategy strategy){ // 혹은 이벤트 객체를 만들어서 파라미터로 받을 수 있음 if(this.count == 0){ this.getBlock(strategy.apply(this)).이벤트전파(strategy); } }

한글로 표현하면

이벤트 전파를 받은 경우 이벤트에 해당하는 조건문 체크 자신이 해당되면 다시 전파재귀. 대각선 이동전략인 경우, 3 방향으로 다시 전파를 하면 될 것같습니다.

의견 추가하기

연관태그

← 목록으로