https://www.acmicpc.net/problem/12100
입력
- N (1 ≤ N ≤ 20)
- 들어올 수 있는 최대 값 2 ~ 1024로 2의 제곱근 형태
문제 해결 프로세스
1. 5번을 움직여 최대 값을 찾기 위해서는 순열이 필요함 (상하좌우)
2. 순열이 만들어졌을 때 해당 방향으로 게임 시작
3. 원본배열 남기고 복사배열 사용
4. 벽으로 밀기, 합치기 2개 메서드 필요
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, answer;
static int[][] original;
static int[] permutation;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
original = new int[N][N];
permutation = new int[5];
StringTokenizer st = null;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
original[i][j] = Integer.parseInt(st.nextToken());
}
}
setPermutation(0);
System.out.println(answer);
}
public static int game(int[][] copy) {
for (int dir : permutation) {
push(copy, dir);
addUp(copy, dir);
push(copy, dir);
}
return findMax(copy);
}
// 벽으로 밀치기
public static int[][] push(int[][] copy, int dir) {
List<Integer> temp = null;
if (dir == 0) { // 상
for (int i = 0; i < N; i++) {
temp = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (copy[j][i] == 0) continue;
temp.add(copy[j][i]);
copy[j][i] = 0;
}
for (int j = 0; j < temp.size(); j++) {
copy[j][i] = temp.get(j);
}
}
} else if (dir == 1) { // 하
for (int i = 0; i < N; i++) {
temp = new ArrayList<>();
for (int j = N - 1; j >= 0; j--) {
if (copy[j][i] == 0) continue;
temp.add(copy[j][i]);
copy[j][i] = 0;
}
for (int j = 0; j < temp.size(); j++) {
copy[N - 1 - j][i] = temp.get(j);
}
}
} else if (dir == 2) { // 좌
for (int i = 0; i < N; i++) {
temp = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (copy[i][j] == 0) continue;
temp.add(copy[i][j]);
copy[i][j] = 0;
}
for (int j = 0; j < temp.size(); j++) {
copy[i][j] = temp.get(j);
}
}
} else if (dir == 3) { // 우
for (int i = 0; i < N; i++) {
temp = new ArrayList<>();
for (int j = N - 1; j >= 0; j--) {
if (copy[i][j] == 0) continue;
temp.add(copy[i][j]);
copy[i][j] = 0;
}
for (int j = 0; j < temp.size(); j++) {
copy[i][N - 1 - j] = temp.get(j);
}
}
}
return copy;
}
//합치기
public static int[][] addUp(int[][] copy, int dir) {
if (dir == 0) { // 상
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N; j++) {
if (copy[i][j] == copy[i + 1][j]) {
copy[i][j] *= 2;
copy[i + 1][j] = 0;
}
}
}
} else if (dir == 1) { // 하
for (int i = N - 1; i > 0; i--) {
for (int j = 0; j < N; j++) {
if (copy[i][j] == copy[i - 1][j]) {
copy[i][j] *= 2;
copy[i - 1][j] = 0;
}
}
}
} else if (dir == 2) { // 좌
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N; j++) {
if (copy[j][i] == copy[j][i + 1]) {
copy[j][i] *= 2;
copy[j][i + 1] = 0;
}
}
}
} else if (dir == 3) { // 우
for (int i = N - 1; i > 0; i--) {
for (int j = 0; j < N; j++) {
if (copy[j][i] == copy[j][i - 1]) {
copy[j][i] *= 2;
copy[j][i - 1] = 0;
}
}
}
}
return copy;
}
public static int findMax(int[][] copy) {
int result = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (result < copy[i][j]) result = copy[i][j];
}
}
return result;
}
public static int[][] copyOriginal() {
int[][] copy = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
copy[i][j] = original[i][j];
}
}
return copy;
}
public static void setPermutation(int depth) {
if (depth == 5) {
int result = game(copyOriginal());
answer = Math.max(result, answer);
return;
}
for (int i = 0; i < 4; i++) {
permutation[depth] = i;
setPermutation(depth + 1);
}
}
}
정리
2048 게임을 많이 해봐서 문제를 이해하는데 시간이 오래 걸리지는 않았다. 단 밀고 합치는 과정에서 약간의 어려움이 있었다.
밀치고, 합치는 과정이 한번에 이루어지는게 아니라서 우선 밀치기 -> 합치기 -> 밀치기를 해야지 게임에서 동작 하나가 된다.
'알고리즘 문제풀이' 카테고리의 다른 글
[백준] 14712 넴모넴모 (Java) (1) | 2024.06.30 |
---|---|
[백준] 13460 구슬탈출2 (Java) (1) | 2024.06.30 |
[백준] 1477 휴게소 세우기 (Java) (0) | 2024.06.26 |
[코드트리] 자율주행 자동차(Java) (0) | 2024.06.24 |
[프로그래머스] 인사고과 Lv.3 (Java) (0) | 2024.06.24 |