[알고스팟] 블록 게임

문제 링크

블록 게임

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • BLOCKGAME
  • 2000ms
  • 65536kb
  • 1313
  • 485 (36%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

시티빌과 비주얼드에 지친 진호와 현환이는 집에 굴러다니는 블럭들을 모아 새로운 게임을 하기로 했습니다. 5×5 크기의 게임판에서 시작해, 둘이 번갈아 가며 블럭을 하나씩 게임판에 내려놓습니다. 블럭은 L 모양으로 구성된 3칸짜리 블럭과 2칸짜리 블럭이 있으며, 항상 게임판에 있는 줄에 맞춰 내려놓아야 합니다. 블럭들은 서로 겹칠 수 없습니다. 다음 그림은 진행중인 게임판의 모습을 보여줍니다.

그림에서 보이는 바와 같이 각 블록은 자유롭게 뒤집거나 회전해서 올려놓을 수 있습니다. 두 사람이 번갈아가며 블록을 올려놓다가 더 올려놓을 수 없게 되면 마지막에 올려놓은 사람이 승리합니다. 진행 중인 게임판이 주어질 때 이번 차례인 사람이 승리할 수 있는 방법이 있는지를 판단하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C≤50)가 주어집니다. 각 테스트 케이스는 다섯 줄에 각 다섯 개의 문자로 구성되며, #는 이미 블록이 놓인 칸, 마침표(.)는 블록이 없는 칸을 의미합니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 이번 차례인 사람이 항상 이길 수 있는 방법이 있다면 WINNING을, 항상 질 수밖에 없다면 LOSING을 출력합니다.

예제 입력

3
.....
.##..
##..#
#.###
..#..
.....
.....
.....
.....
.....
#..##
##.##
##.##
#...#
##.##

예제 출력

WINNING
LOSING
WINNING

어떻게 풀까?

25개의 판 입니다! 게임의 상태를 나타내기 위해 '블록이 놓여있음'과 '놓여있지 않음' 두 가지로 나타난다고 해봅시다!

상태의 수는 2^25 = (2^10)^2*32이고, 32*e6 정도 되는 수이기 때문에 32메가 정도의 저장공간이 필요하겠군요!

다만, 함정이 하나 있습니다.

바로, int 는 4 바이트 라는 것이죠!! 아무 생각 없이 저장공간의 형식을 int로 했다간 런타임 오류가 뜰 겁니다!

573088	BLOCKGAME	상반기는꼭	cpp	1.9KB	런타임 오류		23시간 전
573087	BLOCKGAME	상반기는꼭	cpp	1.9KB	런타임 오류		23시간 전

이처럼 말이죠!

자, 문제를 다시 한번 봅시다.

문제에서 요구하는 사항은 '이겼는지'와 '졌는지' 두 개 밖에 없습니다.

여기서, '아직 해결되지 않음'을 넣으면, 딱 3 가지의 상태만 필요하기 때문에 4 바이트나 잡아먹는 int 대신에 

0~255까지의 256가지 상태를 저장할 수 있는 char를 사용해도 무방합니다! 심지어 char를 써도 굉장히 많은 공간이 남습니다....

이 점만 유의하시면 나머지는 어렵지 않습니다! 이전에 했던것과 비슷하게 문제를 풀면 되기 때문이죠.

블록을 놓을 수 있는지 없는지에 대해 검사를 하고, 놓을 수 있으면 놓은 상태를 비트로 만들어주는 함수를 만들고,

그 상태에서 자신이 이길 수 있는 경우가 하나라도 나오면 그 게임을 이길 수 있는 것이고, 블록을 놓을 수 없거나, 

자신이 놓을 수 있는 블록의 상태에서 이길 수 있는 경우가 없다면 자신이 게임을 지게 되겠죠! 

저같은 경우에는 BLOCK을 미리 만들어놓은 배열을 이용했습니다.

그리고, block이 놓여야 하는데 그 자리에 벽이 이미 세워져 있으면 블록을 놓지 못하게 했습니다.

만약 그렇지 않다면 블록을 놓았죠!

만약, 이에 대해 잘 모르겠다면 이전에 썼던 동적 계획법 - 6을 보시기 바랍니다! (클릭시 이동합니다.)

코드

#include<cstdio>
#include<cstring>
 
char cache[1 << 25];
int conv[256];
char map[6][6] = { 0 };
const char *win[2] = { "LOSING", "WINNING" };
 
// 블럭들
const char block[6][2][2]{
 
        {
            {1,1},
            {1,0}
        },
        {
            {1,1},
            {0,1}
        },
        {
 
            {0,1},
            {1,1}
        },
        {
            {1,0},
            {1,1}
        },
        {
            {1,1},
            {0,0}
        },
        {
            {1,0},
            {1,0}
        }
};
 
int ptb(int r, int c) {
    return 1 << (5 * r + c);
}
 
bool canWin(int state) {
 
    char &ret = cache[state];
    if (ret != -1) return ret;
 
    ret = 0;
 
    //맵 체크
    for (int r = 0; r < 5; r++) {
        for (int c = 0; c < 5; c++) {
            //블럭 6개 체크
            for (int i = 0; i < 6; i++) {
                bool canBuild = true;
 
                //벽 놓을 수 있는지 체크
                for (int k = 0; k < 2 && canBuild; k++) {
                    for (int l = 0; l < 2; l++) {
                        if (map[r + k][c + l] == '#' && block[i][k][l]) {
                            canBuild = false;
                            break;
                        }
                    }
                }
 
                //놓을 수 있으면 벽 놓기
                if (canBuild) {
                    int ns = state;
                    for (int k = 0; k < 2 && canBuild; k++) {
                        for (int l = 0; l < 2; l++) {
                            if (block[i][k][l]) {
                                map[r + k][c + l] = '#';
                                ns |= ptb(r + k, c + l);
                            }
                        }
                    }
 
                    ret = !canWin(ns);
 
                    //다시 블럭 제거
                    for (int k = 0; k < 2 && canBuild; k++) {
                        for (int l = 0; l < 2; l++) {
                            if (block[i][k][l]) {
                                map[r + k][c + l] = '.';
                            }
                        }
                    }
                    //이길 수 있는 경우가 나오면 바로 return
                    if (ret) return ret;
                }
            }
        }
    }
 
    return ret;
}
 
int main() {
    conv['.'] = 0;
    conv['#'] = 1;
    int t;
    scanf("%d\n", &t);
 
    memset(cache, -1, sizeof(cache));
 
    while (t--) {
        int state = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                scanf(" \n%c", &map[i][j]);
                if (map[i][j] == '#') state |= ptb(i, j);
            }
 
            map[i][5] = '#';
            map[5][i] = '#';
        }
        map[5][5] = '#';
        printf("%s\n", win[canWin(state)]);
    }
    return 0;
}

여담

해당 문제는 이미 게임판의 크기가 결정되어 있습니다. 다만, 1 << 25의 부분문제를 가지고, 또 여기서 25 번의 체크를 하기 때문에 굉장히 느리다고 생각할 수 도있습니다! 하지만, 부분 문제가 1 << 25이긴 하더라도, 실제로 저 만큼의 경우의 수가 나오지 않습니다.

블럭이 3개 또는 2개로 뭉쳐있기 때문이죠!

종만북에 의하면 약 160만 개의 경우의 수가 나온다고 하는군요! 덕분에 그렇게 느리진 않습니다.