https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
코드설명
시뮬레이션(Simulation) + 브루트포스(brute force) 문제입니다.
문제에서 주어진대로 모든 경우를 완전탐색하면 됩니다.
문제에서 숫자들을 2048 게임의 원리대로 합치는것은 문제에 주어진대로 구현하면 됩니다.
처음에 4가지 방향을 모두 따로 구현하면서 코드를 줄일 수 있는 방법이 있을까 계속 고민하면서 풀었지만 다른 풀이가 떠오르지 않았습니다.
다만, 구현중에서 가장 문제가 있었던 부분은, Map, 즉 2048 의 숫자를 기록해두는 배열을 처음에 전역배열로 설정해두었기에 storeMap값이 다음 simulate 재귀함수가 실행될경우 바뀐값으로 갱신되어 올바르게 완전탐색을 진행하지 못했었습니다.
전역배열말고, Node[][] storeMap을 각 simulate함수마다 지역변수로 설정하여 해당 문제를 해결할 수 있습니다.
이런 tempMap은 기본적으로 함수 내에서 하도록 습관을 들여야할 것 같습니다.
전역변수에 둘경우 관리가 어렵고, 모든 함수에서 똑같이 접근하므로 각 함수에서의 배열을 따로 선언하지 못하게됩니다.
// public static Node[][] storeMap;
// storeMap = new Node[N][N];
public static void simulate(int level) {
...
...
Node[][] storeMap = new Node[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
storeMap[i][j] = new Node(map[i][j].num, false);
}
}
...
...
}
위와 같은 오류를 찾아낸 방법은, 아래의 예시와 과정입니다.
3
16 2 2
2 2 2
2 2 16
위의 예시입니다.
32가 나오는 과정을 표현해보면,
===0====
16 4 4
4 2 16
0 0 0
===1====
0 16 8
4 2 16
0 0 0
===2====
4 16 8
0 2 16
0 0 0
===3====
4 16 8
2 16 0
0 0 0
===4====
4 32 8
2 0 0
0 0 0
답 : 32
코드
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N,M, K;
public static Node[][] map;
// public static Node[][] storeMap;
public static int answer = 0;
public static int[] dx = {-1, 1, 0, 0};
public 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 = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new Node[N][N];
// storeMap = new Node[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
int a = Integer.parseInt(st.nextToken());
map[i][j] = new Node(a, false);
}
}
// mergeMap(0);
// print(0);
// mergeMap(3);
// print(1);
// mergeMap(0);
// print(2);
// mergeMap(2);
// print(3);
// mergeMap(0);
// print(4);
simulate(0);
System.out.println(answer);
}
public static void simulate(int level) {
//가장 큰 블록값은 매번 검사해도 되지만, 결국 많이 이동한결과가 최대값이므로 매번 하지 않아서 효율성을 개선시키자.
if(level == 5) {
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
answer = Math.max(answer, map[i][j].num);
}
}
return ;
}
Node[][] storeMap = new Node[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
storeMap[i][j] = new Node(map[i][j].num, false);
}
}
for(int dir = 0; dir < 4; dir++) {
//각 방향으로 이동시키자.
//이떄 중요한점은, 한번 이동시키고 난 이후에 merged를 모두 fasel로 초기화 시키고서 작동시켜야한다는것이다.
mergeMap(dir);
simulate(level + 1);
//원상복구.
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
map[i][j].num = storeMap[i][j].num;
map[i][j].merged = false;
}
}
}
}
public static void mergeMap(int dir) {
//시작할떄는 합병여부를 false로 선언하고 시작합니다.
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
map[i][j].merged = false;
}
}
//어떤 방향으로 합쳐질떄.
//위쪽으로 합쳐진다고 가정해보자.
//먼저 해당 부분에 Block이 존재한다면, 이동시킬 방향과 가까운곳부터 블록을 이동시킬 것 이다.
//만약 이동시킬 방향에서 BLock을 못찾거나 이미 해당 블록이 merged 된 상태라면 바로 아래 블록에 넣어준다.
if(dir == 0) {
//블록을 위로 이동시키는 경우.
//N가지의 열을 기준으로 모두 실행됩니다.
for(int col = 0; col < N; col ++) {
//해당 행에서 시작점을 잡아줍니다.
for(int row = 1; row < N; row++) {
int startNum = map[row][col].num;
int nr = row;
//row가 시작점이 되고 그 시작점을 기준으로 While문을 통해서 가장 맨위의 값을 찾아나갑니다.
while(nr >= 0) {
nr = nr + dx[dir];
//만약 범위를 벗어난다면, 가장 맨위칸이 이동할 칸이 될 것 입니다..
if(nr <= -1) {
map[row][col].num = 0;
map[row][col].merged = false;
map[0][col].num = startNum;
map[0][col].merged = false;
break;
}
//만약 해당 칸이 비어있다면, 한칸 올라갑니다.
//다른 작업은 굳이 진행하지 않아도 됩니다.
else if(map[nr][col].num == 0) {
}
//만약 해당 칸이 현재 숫자와 같고, 아직 합쳐진적도 없다면, 해당 부분에서 합쳐주고 종료할 것 입니다.
else if(map[nr][col].num == map[row][col].num && map[nr][col].merged == false) {
map[row][col].num = 0;
map[row][col].merged = false;
map[nr][col].num *= 2;
map[nr][col].merged = true;
break;
}
//만약 해당 칸이 현재 숫자와 같은데, 이미 합쳐져있다면, 한칸 내려야합니다.
else if(map[nr][col].num == map[row][col].num && map[nr][col].merged == true) {
nr -= dx[dir];
map[row][col].num = 0;
map[row][col].merged = false;
map[nr][col].num = startNum;
map[nr][col].merged = false;
break;
}
//만약 서로 다른 숫자라면,
else if(map[nr][col].num != map[row][col].num) {
nr -= dx[dir];
map[row][col].num = 0;
map[row][col].merged = false;
map[nr][col].num = startNum;
map[nr][col].merged = false;
break;
}
}
}
}
}
//하
else if(dir == 1) {
//블록을 위로 이동시키는 경우.
//N가지의 열을 기준으로 모두 실행됩니다.
for(int col = 0; col < N; col ++) {
int startRow = 0;
//해당 행에서 시작점을 잡아줍니다.
for(int row = N-2; row >= 0; row--) {
startRow = row;
int startNum = map[startRow][col].num;
int nr = row;
//row가 시작점이 되고 그 시작점을 기준으로 While문을 통해서 가장 맨위의 값을 찾아나갑니다.
while(nr <= N) {
nr = nr + dx[dir];
//만약 범위를 벗어난다면, 가장 맨위칸이 이동할 칸이 될 것 입니다..
if(nr >= N) {
map[startRow][col].num = 0;
map[startRow][col].merged = false;
map[N-1][col].num = startNum;
map[N-1][col].merged = false;
break;
}
//만약 해당 칸이 비어있다면, 한칸 올라갑니다.
//다른 작업은 굳이 진행하지 않아도 됩니다.
else if(map[nr][col].num == 0) {
}
//만약 해당 칸이 현재 숫자와 같고, 아직 합쳐진적도 없다면, 해당 부분에서 합쳐주고 종료할 것 입니다.
else if(map[nr][col].num == map[startRow][col].num && map[nr][col].merged == false) {
map[startRow][col].num = 0;
map[startRow][col].merged = false;
map[nr][col].num *= 2;
map[nr][col].merged = true;
break;
}
//만약 해당 칸이 현재 숫자와 같은데, 이미 합쳐져있다면, 한칸 내려야합니다.
else if(map[nr][col].num == map[startRow][col].num && map[nr][col].merged == true) {
nr -= dx[dir];
map[startRow][col].num = 0;
map[startRow][col].merged = false;
map[nr][col].num = startNum;
map[nr][col].merged = false;
break;
}
//만약 서로 다른 숫자라면,
else if(map[nr][col].num != map[startRow][col].num) {
nr -= dx[dir];
map[startRow][col].num = 0;
map[startRow][col].merged = false;
map[nr][col].num = startNum;
map[nr][col].merged = false;
break;
}
}
}
}
}
//좌 : dir : 2
else if(dir == 2) {
//블록을 위로 이동시키는 경우.
//N가지의 열을 기준으로 모두 실행됩니다.
for(int row = 0; row < N; row ++) {
//해당 행에서 시작점을 잡아줍니다.
for(int col = 1; col < N; col++) {
int startNum = map[row][col].num;
int nc = col;
//row가 시작점이 되고 그 시작점을 기준으로 While문을 통해서 가장 맨위의 값을 찾아나갑니다.
while(nc >= 0) {
nc = nc + dy[dir];
//만약 범위를 벗어난다면, 가장 맨위칸이 이동할 칸이 될 것 입니다..
if(nc == -1) {
map[row][col].num = 0;
map[row][col].merged = false;
map[row][0].num = startNum;
map[row][0].merged = false;
break;
}
//만약 해당 칸이 비어있다면, 한칸 올라갑니다.
//다른 작업은 굳이 진행하지 않아도 됩니다.
else if(map[row][nc].num == 0) {
}
//만약 해당 칸이 현재 숫자와 같고, 아직 합쳐진적도 없다면, 해당 부분에서 합쳐주고 종료할 것 입니다.
else if(map[row][nc].num == map[row][col].num && map[row][nc].merged == false) {
map[row][col].num = 0;
map[row][col].merged = false;
map[row][nc].num *= 2;
map[row][nc].merged = true;
break;
}
//만약 해당 칸이 현재 숫자와 같은데, 이미 합쳐져있다면, 한칸 내려야합니다.
else if(map[row][nc].num == map[row][col].num && map[row][nc].merged == true) {
nc -= dy[dir];
map[row][col].num = 0;
map[row][col].merged = false;
map[row][nc].num = startNum;
map[row][nc].merged = false;
break;
}
//만약 서로 다른 숫자라면,
else if(map[row][nc].num != map[row][col].num) {
nc -= dy[dir];
map[row][col].num = 0;
map[row][col].merged = false;
map[row][nc].num = startNum;
map[row][nc].merged = false;
break;
}
}
}
}
}
//우 : dir : 3
else if(dir == 3) {
//블록을 위로 이동시키는 경우.
//N가지의 열을 기준으로 모두 실행됩니다.
for(int row = 0; row < N; row ++) {
//해당 행에서 시작점을 잡아줍니다.
for(int col = N-2; col >= 0; col--) {
int startNum = map[row][col].num;
int nc = col;
//row가 시작점이 되고 그 시작점을 기준으로 While문을 통해서 가장 맨위의 값을 찾아나갑니다.
while(nc <= N) {
nc = nc + dy[dir];
//만약 범위를 벗어난다면, 가장 맨위칸이 이동할 칸이 될 것 입니다..
if(nc == N) {
map[row][col].num = 0;
map[row][col].merged = false;
map[row][N-1].num = startNum;
map[row][N-1].merged = false;
break;
}
//만약 해당 칸이 비어있다면, 한칸 올라갑니다.
//다른 작업은 굳이 진행하지 않아도 됩니다.
else if(map[row][nc].num == 0) {
}
//만약 해당 칸이 현재 숫자와 같고, 아직 합쳐진적도 없다면, 해당 부분에서 합쳐주고 종료할 것 입니다.
else if(map[row][nc].num == map[row][col].num && map[row][nc].merged == false) {
map[row][col].num = 0;
map[row][col].merged = false;
map[row][nc].num *= 2;
map[row][nc].merged = true;
break;
}
//만약 해당 칸이 현재 숫자와 같은데, 이미 합쳐져있다면, 한칸 내려야합니다.
else if(map[row][nc].num == map[row][col].num && map[row][nc].merged == true) {
nc -= dy[dir];
map[row][col].num = 0;
map[row][col].merged = false;
map[row][nc].num = startNum;
map[row][nc].merged = false;
break;
}
//만약 서로 다른 숫자라면,
else if(map[row][nc].num != map[row][col].num) {
nc -= dy[dir];
map[row][col].num = 0;
map[row][col].merged = false;
map[row][nc].num = startNum;
map[row][nc].merged = false;
break;
}
}
}
}
}
}
public static void print(int level) {
System.out.println("==="+level+"====");
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
System.out.print(" "+map[i][j].num);
}
System.out.println();
}
}
}
class Node{
int num;
boolean merged = false;
public Node(int num, boolean merged) {
this.num = num;
this.merged = merged;
}
}'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 9663 N-Queen - 브루트포스(BruteForce) + 시간초과(TimeOut) JAVA (0) | 2022.07.11 |
|---|---|
| [백준] 14502 연구소 - 브루트포스(BruteForce) + BFS(너비우선탐색) + 조합(Combination) JAVA (0) | 2022.03.05 |
| [백준] 13305번 주유소 - 그리디(Greedy, 탐욕법) JAVA (0) | 2021.12.23 |
| [백준] 1541번 잃어버린 괄호 - 문자열 파싱(Parsing) + Stack(스택) + 그리디(탐욕법, Greedy) JAVA (0) | 2021.12.22 |
| [백준] 11399번 - ATM (0) | 2021.12.20 |