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; } }