이번에 풀어본 문제는
백준 12100번 2048 입니다.
📕 문제 링크
❗️코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int max_val = Integer.MIN_VALUE;
static int N;
static int [][] map;
static boolean [][] visited;
static int [] dx = {-1,1,0,0};
static int [] dy = {0,0,-1,1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for(int i = 0; i < N; ++i)
{
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; ++j)
{
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] > max_val)
{
max_val = map[i][j];
}
}
}
comb(new ArrayList<>());
System.out.print(max_val);
}
static void comb(List<Integer> al)
{
if(al.size() == 5)
{
int [][] copy = new int[N][N];
for(int i = 0; i < N; ++i) System.arraycopy(map[i],0,copy[i],0,N);
play(al,copy);
return;
}
for(int i = 0; i < 4; ++i)
{
List<Integer> tmp = new ArrayList<>(al);
tmp.add(i);
comb(tmp);
}
}
static void play(List<Integer> al, int [][] copy)
{
int tmp_val = Integer.MIN_VALUE;
for(int dir : al)
{
visited = new boolean[N][N];
switch(dir)
{
// 상
case 0:
{
for(int j = 0; j < N; ++j)
{
next : for(int i = 1; i < N; ++i)
{
if(copy[i][j] > 0)
{
int num = copy[i][j];
int mx = i + dx[dir];
int my = j + dy[dir];
while(true)
{
if(!isValid(mx,my) || visited[mx][my]) break;
if(copy[mx][my] > 0)
{
if(copy[mx][my] == num)
{
copy[mx][my] = num * 2;
if(copy[mx][my] > tmp_val) tmp_val = copy[mx][my];
copy[i][j] = 0;
visited[mx][my] = true;
continue next;
}
else break;
}
mx += dx[dir];
my += dy[dir];
}
// 1칸 아래로
mx += dx[1];
my += dy[1];
if(mx != i)
{
copy[mx][my] = num;
copy[i][j] = 0;
}
}
}
}
break;
}
// 하
case 1:
{
for(int j = 0; j < N; ++j)
{
next : for(int i = N-2; i >= 0; --i)
{
if(copy[i][j] > 0)
{
int num = copy[i][j];
int mx = i + dx[dir];
int my = j + dy[dir];
while(true)
{
if(!isValid(mx,my) || visited[mx][my]) break;
if(copy[mx][my] > 0)
{
if(copy[mx][my] == num)
{
copy[mx][my] = num * 2;
if(copy[mx][my] > tmp_val) tmp_val = copy[mx][my];
copy[i][j] = 0;
visited[mx][my] = true;
continue next;
}
else break;
}
mx += dx[dir];
my += dy[dir];
}
// 1칸 위로
mx += dx[0];
my += dy[0];
if(mx != i)
{
copy[mx][my] = num;
copy[i][j] = 0;
}
}
}
}
break;
}
// 좌
case 2:
{
for(int i = 0; i < N; ++i)
{
next : for(int j = 1; j < N; ++j)
{
if(copy[i][j] > 0)
{
int num = copy[i][j];
int mx = i + dx[dir];
int my = j + dy[dir];
while(true)
{
if(!isValid(mx,my) || visited[mx][my]) break;
if(copy[mx][my] > 0)
{
if(copy[mx][my] == num)
{
copy[mx][my] = num * 2;
if(copy[mx][my] > tmp_val) tmp_val = copy[mx][my];
copy[i][j] = 0;
visited[mx][my] = true;
continue next;
}
else break;
}
mx += dx[dir];
my += dy[dir];
}
// 1칸 우측
mx += dx[3];
my += dy[3];
if(my != j)
{
copy[mx][my] = num;
copy[i][j] = 0;
}
}
}
}
break;
}
// 우
case 3:
{
for(int i = 0; i < N; ++i)
{
next : for(int j = N-2; j >= 0; --j)
{
if(copy[i][j] > 0)
{
int num = copy[i][j];
int mx = i + dx[dir];
int my = j + dy[dir];
while(true)
{
if(!isValid(mx,my) || visited[mx][my]) break;
if(copy[mx][my] > 0)
{
if(copy[mx][my] == num)
{
copy[mx][my] = num * 2;
if(copy[mx][my] > tmp_val) tmp_val = copy[mx][my];
copy[i][j] = 0;
visited[mx][my] = true;
continue next;
}
else break;
}
mx += dx[dir];
my += dy[dir];
}
// 1칸 왼쪽
mx += dx[2];
my += dy[2];
if(my != j)
{
copy[mx][my] = num;
copy[i][j] = 0;
}
}
}
}
break;
}
}
}
max_val = Math.max(tmp_val,max_val);
}
static boolean isValid(int x, int y)
{
return x >= 0 && y >= 0 && x < N && y < N;
}
}
📝 풀이
2048 게임을 조금 단순화하여 새로운 블록은 생기지 않으며 최대 5회까지 이동했을 때, 만들 수 있는 가장 큰 블록의 수를 출력하는 문제입니다.
이동명령은 상,하,좌,우로 4가지 경우가 존재하므로 이들로 만들 수 있는 5회간의 이동조합을 만들고, play함수에 넘겨 해당 경우에 따른 최댓값을 구해주는 완전탐색을 활용했습니다.
최댓값의 변동은 두 블록이 합쳐지는 순간에만 생기므로, 매 반복마다 조건을 넣어주기 보다는 블록의 합체가 이루어졌을 때, 최댓값과 비교하여 더 커졌으면 갱신해주는 방식을 택했습니다. 이 방법을 사용하려면, 블록 합체가 한번도 일어나지 않을 경우를 대비하여 입력과정에서 초기 map에서의 최댓값을 저장하고 있어야 합니다.
📜 후기
상,하,좌,우로 이동하는 코드가 다르다 보니 전체적으로 조금 길어보이지만 난이도에 비해 풀만했던 문제였습니다.
학창시절 가볍게 즐겼던 게임을 구현해보니 반가웠고, 좀 더 재미있게 풀 수 있었습니다 ㅎㅎ
머무르지 않기!