ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 블록게임
    알고리즘/algospot 2016. 8. 1. 22:11

    조합게임의 예제로 나온 문제. 모두가 최선을 다했을 때 이길 수 있는 경우에 대한 것은 앞에서 설명했으니 넘어가고 블록과 보드게임의 상태를 비트 연산을 이용해 어떻게 깔끔히 표현했는지에 주목하자.


     
    void precalc() {
    	for(int y = 0; y < 4; y++)
    		for (int x = 0; x < 4; x++) {
    			vector<int> cells;
    			for (int dy = 0; dy < 2; dy++)
    				for (int dx = 0; dx < 2; dx++)
    					cells.push_back(cell(y + dy, x + dx));
    			int square = cells[0] + cells[1] + cells[2] + cells[3];
    
    			for (int i = 0; i < 4; i++)
    				moves.push_back(square - cells[i]);
    		}
    
    	for(int i=0; i<5; i++)
    		for (int j = 0; j < 4; j++) {
    			moves.push_back(cell(i, j) + cell(i, j+1));
    			moves.push_back(cell(j, i) + cell(j+1, i));
    		}
    }
    
    char play(int board) {
    	char& ret = cache[board];
    
    	if (ret != -1)
    		return ret;
    
    	ret = 0;
    
    	for(int i=0; i<moves.size(); i++)
    		if((moves[i] & board) == 0)
    			if (!play(board | moves[i])) {
    				ret = 1;
    				break;
    			}
    
    	return ret;
    }
    

    먼저 5*5 board판인 점을 이용해서 비트를 이용해 각각의 상태를 표현한다는 접근법부터 놀랍다. 나라면 또 board의 상태에 따라서 행렬을 그리고 이중포인터 사용하고 지저분해졌을것 같은데 저자는 board의 상태를 비트로 표현해 int변수 만으로 표현해줄 수 있었다.

    또한 precalc()는 모든 위치에서 블록을 둘 수 있는 경우의 수들을 저장해둔것인데 모든 위치에 대해 둘 수 있는 블록의 경우의 수를 미리 계산한 것도 멋지고 또다시 주목할만한 부분은 L모양의 블록을 비트로 표현할 때 square값에다가 각각의 cell값을 빼준 것이다. 생각하는 방식이 나와 다른 것 같다.

    play함수 내에서 블럭을 놓을 수 있는지를 간단히 AND 연산으로 처리했고 블럭을 놓는 경우는 OR연산으로 처리했다. 고수들만이 이런 경지에 오르는 것이 아닐까 싶다.


    '알고리즘 > algospot' 카테고리의 다른 글

    카쿠로  (0) 2016.12.11
    회전초밥  (0) 2016.08.01
    조합게임  (0) 2016.07.25
    ASYMTLING  (0) 2015.02.21
    NUMB3RS  (0) 2015.02.21

    댓글

Designed by Tistory.