Notice
Recent Posts
Link
- Today
- Total
hye-log
[백준]12100번 2048 (Easy)(JAVA) 본문
0. 문제 링크
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
1. 문제 설명
1) 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값 구하기
2. 입출력
// input
3
2 2 2
4 4 4
8 8 8
// output
16
3. 코드
import java.io.*;
import java.util.*;
public class b12100 {
private static List<Integer> l;
private static int N;
private static int[][] map;
private static int[] nums = {1, 2, 3, 4};
private static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
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());
}
}
recursive(new int[5], 0); // 5번 반복
System.out.println(max); // 최대값 출력
}
private static void recursive(int[] sel, int idx) {
// basis part
if(idx == sel.length) { // 다 선택했으면
int[][] arr = new int[N][N]; // 새로운 맵 만들어서 map 복사
for (int i = 0; i < N; i++) {
System.arraycopy(map[i], 0, arr[i], 0, N);
}
for (int i = 0; i < sel.length; i++) { // 선택한 command만큼 move
arr = move(arr, sel[i]);
}
for (int i = 0; i < N; i++) { // 최대값 찾기
for (int j = 0; j < N; j++) {
max = Math.max(max, arr[i][j]);
}
}
return;
}
// inductive part
for (int i = 0; i < nums.length; i++) { // 4개 중에 중복해서 5개 구하기(중복 순열)
sel[idx] = nums[i];
recursive(sel, idx + 1);
}
}
private static int[][] move(int[][] arr, int command) {
switch(command) { // command 방향 대로 한 줄 빼기 -> 값이 같으면 연산하기 -> 다시 배열에 넣기
case 1:
for(int i = 0; i < N; i++) { // 리스트로 빼기
l = new ArrayList<Integer>();
for(int j = 0; j < N; j++) {
if(arr[j][i] > 0) {
l.add(arr[j][i]);
}
}
for(int j = 0; j < l.size(); j++) { // 값이 같으면 연산하기
if(j+1 < l.size() && l.get(j).equals(l.get(j+1))) {
int temp = l.get(j);
l.set(j, temp * 2);
l.remove(j+1);
}
}
for(int j = 0; j < N; j++) { // 다시 배열에 넣기
if(j < l.size()) {
arr[j][i] = l.get(j);
} else {
arr[j][i] = 0;
}
}
}
break;
case 2:
for(int i = 0; i < N; i++) { // 리스트로 빼기
l = new ArrayList<Integer>();
for(int j = N-1; j >= 0; j--) {
if(arr[j][i] > 0) {
l.add(arr[j][i]);
}
}
for(int j = 0; j < l.size(); j++) { // 값이 같으면 연산하기
if(j+1 < l.size() && l.get(j).equals(l.get(j+1))) {
int temp = l.get(j);
l.set(j, temp * 2);
l.remove(j+1);
}
}
for(int j = 0; j < N; j++) { // 다시 배열에 넣기
if(j < l.size()) {
arr[N-1-j][i] = l.get(j);
} else {
arr[N-1-j][i] = 0;
}
}
}
break;
case 3:
for(int i = 0; i < N; i++) { // 리스트로 빼기
l = new ArrayList<Integer>();
for(int j = 0; j < N; j++) {
if(arr[i][j] > 0) {
l.add(arr[i][j]);
}
}
for(int j = 0; j < l.size(); j++) { // 값이 같으면 연산하기
if(j+1 < l.size() && l.get(j).equals(l.get(j+1))) {
int temp = l.get(j);
l.set(j, temp * 2);
l.remove(j+1);
}
}
for(int j = 0; j < N; j++) { // 다시 배열에 넣기
if(j < l.size()) {
arr[i][j] = l.get(j);
} else {
arr[i][j] = 0;
}
}
}
break;
case 4:
for(int i = 0; i < N; i++) { // 리스트로 빼기
l = new ArrayList<Integer>();
for(int j = N-1; j >= 0; j--) {
if(arr[i][j] > 0) {
l.add(arr[i][j]);
}
}
for(int j = 0; j < l.size()-1; j++) { // 값이 같으면 연산하기
if(j+1 < l.size() && l.get(j).equals(l.get(j+1))) {
int temp = l.get(j);
l.set(j, temp * 2);
l.remove(j+1);
}
}
for(int j = 0; j < N; j++) { // 다시 배열에 넣기
if(j < l.size()) {
arr[i][N-1-j] = l.get(j);
} else {
arr[i][N-1-j] = 0;
}
}
}
break;
}
return arr;
}
}
실행 결과
4. 회고
1) 5번을 위, 아래, 왼쪽, 오른쪽 중 어느 방향으로 움직일지 결정한 후 모든 경우의 수를 시뮬레이션 함
2) 선택한 방향으로 움직이는 블록을 리스트에 저장한 후, 0이면 패스, 같은 값이면 2배 처리하여 계산한 후, 다시 배열에 저장함
3) 5번 움직인 배열에서 블록의 최대값을 찾아 출력
5. Github
https://github.com/iihye/Algorithm/blob/main/Baekjoon/b12100.java
728x90
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준]1157번 단어 공부(JAVA) (0) | 2023.08.13 |
---|---|
[백준]1152번 단어의 개수(JAVA) (0) | 2023.08.12 |
[백준]16935 배열 돌리기3(JAVA) (0) | 2023.08.10 |
[백준]16926번 배열 돌리기1(JAVA) (0) | 2023.08.10 |
[백준]7576번 토마토(JAVA) (0) | 2023.08.10 |
Comments