BOJ 12100
2021-01-22
위 문제는 백준 사이트의 알고리즘 12100 문제에 관한 설명입니다.
문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.
이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을
상하좌우 네 방향 중 하나로 이동시키는 것이다.
이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다.
한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.
(실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만,
이 문제에서 블록이 추가되는 경우는 없다)
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다.
0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다.
블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다.
블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ12100 {
static int N;
static int answer;
static int map[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
StringTokenizer st;
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());
}
}
answer = Integer.MIN_VALUE;
gamePlay(0);
System.out.println(answer);
}
private static void gamePlay(int count) {
if (count == 5) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
answer = Math.max(answer, map[i][j]);
}
}
return;
}
int tempMap[][] = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
tempMap[i][j] = map[i][j];
}
}
for (int i = 0; i < 4; i++) {
swipe(i);
gamePlay(count + 1);
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
map[j][k] = tempMap[j][k];
}
}
}
}
private static void swipe(int direction) {
if (direction == 0) {
for (int i = 0; i < N; i++) {
int index = 0;
int block = 0;
for (int j = 0; j < N; j++) {
if (map[j][i] != 0) {
if (block == map[j][i]) {
map[index - 1][i] = block * 2;
block = 0;
map[j][i] = 0;
} else {
block = map[j][i];
map[j][i] = 0;
map[index][i] = block;
index++;
}
}
}
}
} else if (direction == 1) {
for (int i = 0; i < N; i++) {
int index = N - 1;
int block = 0;
for (int j = N - 1; j >= 0; j--) {
if (map[j][i] != 0) {
if (block == map[j][i]) {
map[index + 1][i] = block * 2;
block = 0;
map[j][i] = 0;
} else {
block = map[j][i];
map[j][i] = 0;
map[index][i] = block;
index--;
}
}
}
}
} else if (direction == 2) {
for (int i = 0; i < N; i++) {
int index = 0;
int block = 0;
for (int j = 0; j < N; j++) {
if (map[i][j] != 0) {
if (block == map[i][j]) {
map[i][index - 1] = block * 2;
block = 0;
map[i][j] = 0;
} else {
block = map[i][j];
map[i][j] = 0;
map[i][index] = block;
index++;
}
}
}
}
} else {
for (int i = 0; i < N; i++) {
int index = N - 1;
int block = 0;
for (int j = N - 1; j >= 0; j--) {
if (map[i][j] != 0) {
if (block == map[i][j]) {
map[i][index + 1] = block * 2;
block = 0;
map[i][j] = 0;
} else {
block = map[i][j];
map[i][j] = 0;
map[i][index] = block;
index--;
}
}
}
}
}
}
}
이번 문제는 시뮬레이션 문제 였습니다.
static int N;
static int answer;
static int map[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
StringTokenizer st;
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());
}
}
answer = Integer.MIN_VALUE;
입력부 입니다.
맵의 사이즈인 N을 입력받고 N x N 사이즈의 맵에 값을 입력받습니다.
그리고 최댓값을 구하기 위한 answer 변수에 가장 작은값을 넣어줍니다.
private static void gamePlay(int count) {
if (count == 5) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
answer = Math.max(answer, map[i][j]);
}
}
return;
}
int tempMap[][] = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
tempMap[i][j] = map[i][j];
}
}
for (int i = 0; i < 4; i++) {
swipe(i);
gamePlay(count + 1);
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
map[j][k] = tempMap[j][k];
}
}
}
}
메인 함수에서는 gamePlay 함수에 count로 0을 넣어줬습니다.
재귀함수 형태로 구현함으로써 기저 조건인 count가 5라면
5회에 대한 이동이 되었으니 현재 있는 맵에서
구할 수 있는 가장 큰 값을 계산해서 answer와 비교합니다.
그리고 더 큰 값을 answer에 갱신 시켜줍니다.
tempMap 함수는 임시로 map과 같은 사이즈, 값을 저장시킬 배열입니다.
그리고 4 방향을 돌려가면서 방향마다 한번씩 쓸어넘기면서 재귀시킵니다.
재귀를 빠져 나온다면 가장 큰 값에 대한 정보가 tempMap에서 map으로 옮겨줍시다.
private static void swipe(int direction) {
if (direction == 0) {
for (int i = 0; i < N; i++) {
int index = 0;
int block = 0;
for (int j = 0; j < N; j++) {
if (map[j][i] != 0) {
if (block == map[j][i]) {
map[index - 1][i] = block * 2;
block = 0;
map[j][i] = 0;
} else {
block = map[j][i];
map[j][i] = 0;
map[index][i] = block;
index++;
}
}
}
}
} else if (direction == 1) {
for (int i = 0; i < N; i++) {
int index = N - 1;
int block = 0;
for (int j = N - 1; j >= 0; j--) {
if (map[j][i] != 0) {
if (block == map[j][i]) {
map[index + 1][i] = block * 2;
block = 0;
map[j][i] = 0;
} else {
block = map[j][i];
map[j][i] = 0;
map[index][i] = block;
index--;
}
}
}
}
} else if (direction == 2) {
for (int i = 0; i < N; i++) {
int index = 0;
int block = 0;
for (int j = 0; j < N; j++) {
if (map[i][j] != 0) {
if (block == map[i][j]) {
map[i][index - 1] = block * 2;
block = 0;
map[i][j] = 0;
} else {
block = map[i][j];
map[i][j] = 0;
map[i][index] = block;
index++;
}
}
}
}
} else {
for (int i = 0; i < N; i++) {
int index = N - 1;
int block = 0;
for (int j = N - 1; j >= 0; j--) {
if (map[i][j] != 0) {
if (block == map[i][j]) {
map[i][index + 1] = block * 2;
block = 0;
map[i][j] = 0;
} else {
block = map[i][j];
map[i][j] = 0;
map[i][index] = block;
index--;
}
}
}
}
}
}
4 방향에 대해서 쓸어낼때의 동작을 하는 swipe함수입니다.
해당 index 번째와, block은 해당 라인에서 하나씩 확인하면서
더할 수 있는값인가, 아닌가를 확인하고 로직을 처리합니다.