백준 12100번: 2048(Easy)

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;

public class Main {

private static boolean Debug = true;

private static int MapSize;

private static int[][] OriginMap;

private static int[][] CopyMap;

private static Queue<Integer>[] bQueue;

static int MaxNum = 0;

final static int north = 0, east = 1, south = 2, west = 3;

public static void main(String[] args) throws Exception {

BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;

// 맵 크기, 사과 개수

MapSize = Integer.parseInt(br.readLine());

MaxNum = 0;

// 맵 생성

OriginMap = new int[MapSize][];

for (int i = 0; i < MapSize; i++) {

OriginMap[i] = new int[MapSize];

st = new StringTokenizer(br.readLine());

int item;

for (int j = 0; j < MapSize; j++) {

item = Integer.parseInt(st.nextToken());

OriginMap[i][j] = item;

// 합칠 수 없는 경우, 처음 주어진 수가 가장 크다.

if (MaxNum < item) {

MaxNum = item;

}

}

}

// 큐 초기화 (블록을 옮기는 데 사용된다.

bQueue = new LinkedList[MapSize];

for (int i = 0; i < MapSize; i++) {

bQueue[i] = new LinkedList<>();

}

// 00000 ~ 33333

int[] bitmasking = new int[5];

execute(bitmasking, 0);

// 시간 출력

System.out.println(MaxNum);

}

private static void execute(int[] bitmask, int index) {

// 비트마스킹을 조립

if (index <= 4) {

for (int i = 0; i < 4; i++) {

bitmask[index] = i;

execute(bitmask, index + 1);

}

return;

}

// 맵초기화

initMap();

// 실행

int rIndex;

for (int i = 0; i < 5; i++) {

rIndex = bitmask[i];

tiltMap(rIndex);

}

}

private static void initMap() {

// Merge를 위한 지도 초기화

CopyMap = new int[MapSize][];

for (int i = 0; i < MapSize; i++) {

CopyMap[i] = new int[MapSize];

for (int j = 0; j < MapSize; j++) {

int num = OriginMap[i][j];

if (num != 0) { // 0은 빈공간

CopyMap[i][j] = num;

} else {

// non-target

}

}

}

}

private static void tiltMap(int rIndex) {

// log("tiltMap(%d)", rIndex);

// 정방향|역방향

// 행기준|열기준

boolean good = (rIndex == west || rIndex == north);

boolean isRow = (rIndex == west || rIndex == east);

// 방향에 따른 병합 및 매칭

int j_start = (good ? 0 : MapSize - 1);

int j_end = (good ? MapSize : -1);

int j_add = (good ? 1 : -1);

for (int i = 0; i < MapSize; i++) {

// 1. 큐에 대입

int j = j_start;

while (j != j_end) {

// 행기준 열기준에 따라 값을 큐에 넣는다. 

int item = isRow ? CopyMap[i][j] : CopyMap[j][i];

if (item != 0) {

bQueue[i].add(item);

// 값을 옮기면, 해당 자리는 빈공간으로 체크

if (isRow) {

CopyMap[i][j] = 0;

} else {

CopyMap[j][i] = 0;

}

}

j += j_add;

}

// 2. 머지

bQueue[i] = mergeBlock(bQueue[i]);

// 3. 맵에 매칭

j = j_start;

while (j != j_end) {

if (!bQueue[i].isEmpty()) {

if (isRow) {

CopyMap[i][j] = bQueue[i].poll();

// log("큐 방출 [%d][%d] = %d", i, j, CopyMap[i][j].num);

} else {

CopyMap[j][i] = bQueue[i].poll();

// log("큐 대입 [%d][%d] = %d", j, i, CopyMap[j][i].num);

}

} else {

break;

}

j += j_add;

}

}

}

static Queue<Integer> rQue;

private static Queue<Integer> mergeBlock(Queue<Integer> que) {

// 반환을 위한 큐

rQue = new LinkedList<>();

// 합치고

int item1 = 0, item2 = 0;

while (true) {

// 합칠 대상1 픽업

if (item1 == 0) {

if (!que.isEmpty()) {

item1 = que.poll();

} else {

// 큐가 비었으므로

break;

}

}

// 합칠 대상2 픽업

if (item2 == 0) {

if (!que.isEmpty()) {

item2 = que.poll();

} else {

// 비교대상이 없으므로

rQue.add(item1);

break;

}

}

// item1과 item2를 합친다.

if (item1 == item2) {

int mergeNum = item1 * 2;

rQue.add(mergeNum);

// 최고값 측정

if (MaxNum < mergeNum) {

MaxNum = mergeNum;

}

item1 = 0;

item2 = 0;

} else { // 합칠수 없는 경우, 이전 비교대상은 rQue에 넣는다.

rQue.add(item1);

item1 = item2; // 다음비교 대상이 첫번 째가 된다.

item2 = 0;

}

}

return rQue;

}

public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}

public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}

}