https://algospot.com/judge/problem/read/BLOCKGAME
algospot.com :: BLOCKGAME
블록 게임 문제 정보 문제 시티빌과 비주얼드에 지친 진호와 현환이는 집에 굴러다니는 블럭들을 모아 새로운 게임을 하기로 했습니다. 5×5 크기의 게임판에서 시작해, 둘이 번갈아 가며 블럭을
algospot.com
코드설명
동적계획법(Dynamic Programming, DP) + 게임이론(Game Theory) 을 활용합니다.
이 문제의 경우 메모리초과를 고려해야 합니다.
처음에 아래와 같이 제출하면 메모리 초과가 납니다.
이유는, byte[]는 1칸의 데이터당 8bit의 크기입니다.
byte 배열 사이즈는 1<<25 로써 2^25 (= 33,554,432 ) 개입니다.
즉,총 메모리 사용량은 2^25 * 2^8 = 2^32 = 4294967296(42억) 정도의 크기입니다.
이는 문제의 메모리인 65536 kb 크기보다 훨씬 넘어서는 크기입니다.
명확한 비교를 위해 65536 kb는 몇 사이즈일지 계산해봅시다. 65536kb = 2^16 bit * 2^10 bit 입니다. 즉, 2^26 의 크기입니다.
메모리 사이즈 초과로 런타임 에러가 발생하는 이유를 알 수 있습니다.
그대신에 boolean 으로 2^1 크기. 즉, 1bit 크기의 boolean을 사용함으로써 2^26 개를 딱 맞추어서 사용할 수 있습니다.
또, 이 경우 boolean으로만 표현해도 괜찮을까?라는 생각이 듭니다.
이 문제의 경우 비기는 경우는 없고, 반드시 이기는 경우와 지는 경우 2가지만 있기에 이기는 경우만 캐싱해서 처리합니다.(다만, 지는 경우를 캐싱하지 않아서 시간이 조금 더 추가되겠습니다.)
코드
첫번쨰 오류 코드. (byte를 사용하면서 메모리 초과 발생)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static int C, N, W, H, K;
private static int answer = 0;
private static char[][] arr;
//가능한 모든 블록 위치를 저장하는 리스트입니다.
private static List<Integer> moves = new ArrayList<>();
//게임상태에 대한 캐시(메모이제이션)
private static byte[] cache = new byte[1 << 25];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//가능한 모든 블록 위치 미리 계산
precalc();
//게임상태에 대한 캐시(메모이제이션)
cache = new byte[1 << 25];
Arrays.fill(cache, (byte) -1);
arr = new char[5][5];
C = Integer.parseInt(st.nextToken());
while(C-- > 0){
int board = 0;
for(int i=0;i<5;i++) {
st = new StringTokenizer(br.readLine());
String str = st.nextToken();
for(int j=0;j<5;j++) {
arr[i][j] = str.charAt(j);
if(arr[i][j] == '#') {
board += cell(i, j);
}
}
}
byte result = play(board);
if(result == 1) {
System.out.println("WINNING");
}else {
System.out.println("LOSING");
}
System.out.println(moves.size());
System.out.println(cache.length);
}
}
private static int cell(int r, int c) {
return 1 << (r * 5 + c);
}
//가능한 모든 블록 위치를 미리 계산
private static void precalc() {
//'ㄴ'자 모양 블록 계산
for(int r=0; r<4; r++) {
for(int c =0; c<4; c++) {
List<Integer> cells = new ArrayList<>();
for(int dr = 0; dr < 2; dr++) {
for(int dc = 0; dc < 2; dc++) {
cells.add(cell(r + dr, c + dc));
}
}
int square = cells.get(0) + cells.get(1) + cells.get(2) + cells.get(3);
for(int i=0; i<4; i++) {
moves.add(square - cells.get(i));
}
}
}
//두 칸짜리 블록 계산
for(int i=0; i<5; i++) {
for(int j=0; j<4; j++) {
//가로방향 두 칸 블록
moves.add(cell(i, j) + cell(i, j + 1));
//세로방향 두 칸 블록
moves.add(cell(j, i) + cell(j + 1, i));
}
}
}
static byte play(int board) {
if(cache[board] != (byte) -1) {
return cache[board];
}
byte ret = 0;
//가능한 모든 움직임에 대해 검사
for(int i=0;i<moves.size();i++) {
//블록을 놓을 수 있는 경우
if( (moves.get(i) & board) == 0) {
//다음 상태에서 상대방이 지면 현재 플레이어가 이깁니다.
if( play(moves.get(i) | board) == 0 ) {
ret = 1;
break;
}
}
}
return cache[board] = ret;
}
}
정답코드입니다. boolean 을 사용하여 메모리 캐싱합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static int C, N, W, H, K;
private static int answer = 0;
private static char[][] arr;
//가능한 모든 블록 위치를 저장하는 리스트입니다.
private static List<Integer> moves = new ArrayList<>();
//게임상태에 대한 캐시(메모이제이션)
private static boolean[] cache;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//가능한 모든 블록 위치 미리 계산
precalc();
//게임상태에 대한 캐시(메모이제이션)
cache = new boolean[1 << 25];
// Arrays.fill(cache, (byte) -1);
arr = new char[5][5];
C = Integer.parseInt(st.nextToken());
while(C-- > 0){
int board = 0;
for(int i=0;i<5;i++) {
st = new StringTokenizer(br.readLine());
String str = st.nextToken();
for(int j=0;j<5;j++) {
arr[i][j] = str.charAt(j);
if(arr[i][j] == '#') {
board += cell(i, j);
}
}
}
boolean result = play(board);
if(result == true) {
System.out.println("WINNING");
}else {
System.out.println("LOSING");
}
}
}
private static int cell(int r, int c) {
return 1 << (r * 5 + c);
}
//가능한 모든 블록 위치를 미리 계산
private static void precalc() {
//'ㄴ'자 모양 블록 계산
for(int r=0; r<4; r++) {
for(int c =0; c<4; c++) {
List<Integer> cells = new ArrayList<>();
for(int dr = 0; dr < 2; dr++) {
for(int dc = 0; dc < 2; dc++) {
cells.add(cell(r + dr, c + dc));
}
}
int square = cells.get(0) + cells.get(1) + cells.get(2) + cells.get(3);
for(int i=0; i<4; i++) {
moves.add(square - cells.get(i));
}
}
}
//두 칸짜리 블록 계산
for(int i=0; i<5; i++) {
for(int j=0; j<4; j++) {
//가로방향 두 칸 블록
moves.add(cell(i, j) + cell(i, j + 1));
//세로방향 두 칸 블록
moves.add(cell(j, i) + cell(j + 1, i));
}
}
}
static boolean play(int board) {
if(cache[board] != false) {
return cache[board];
}
boolean ret = false;
//가능한 모든 움직임에 대해 검사
for(int i=0;i<moves.size();i++) {
//블록을 놓을 수 있는 경우
if( (moves.get(i) & board) == 0) {
//다음 상태에서 상대방이 지면 현재 플레이어가 이깁니다.
if( play(moves.get(i) | board) == false ) {
ret = true;
break;
}
}
}
return cache[board] = ret;
}
}