[백준] 12100. 2048 (Easy) (자바 JAVA)

[ 문제 ]  [백준] 12100. 2048 (Easy) (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

---

# 접근 방법 및 풀이 

 

• 완탐 + 백트래킹 문제다.
• dfs로 상하좌우 4방향에 대해서 5회까지 다 이동시켜보고 그때 최대값을 구하면 된다.
• 여기서 백트래킹은 방향을 정하고, 그 방향으로 이동시키기 전에 먼저 원본 map상태를 백업해두어야한다.
• 어떤 방향으로 블럭을 이동 시킨후에 다음회차로 넘어간 뒤, 다시 돌아왔을때 그 해당 회차에 다른 방향으로도 가보아야 하므로 다시 백업해둔 원본 map으로 바꿔주고 다음 방향을 살펴보면 된다.
• 여기서 핵심은 방향에 따라서 모든 블럭을 움직일때 체크해주어야 하는 부분이다.
• 같은 값을 갖는 두 블럭이 충돌할 경우 하나로 합쳐진다. 2와 2가 만나면 => 4가 된다.
• 근데 한번 합쳐진 블럭은 또 같은 값을 갖는 블럭을 만나도 합쳐질 수 없다. 이부분에 대해서 확인하기 위해 boolean 2차원 check배열을 만들어주었다. 만약, 같은 값끼리 만나서 합쳐졌을 경우 true로 바꿔주고 true일 경우에는 같은 값을 갖는 블럭이라도 합쳐질 수 없도록 했다.
• 그리고 블럭을 움직일때는 블럭값이 0이 아닐경우 go()메서드를 통해 현재 위치에서 다음 위치로 갈 곳을 Point클래스로 반환 받는다.
• 현재위치를 = 0으로 초기화하고 다음으로 위치에 블럭값을 +더해주면 된다. 더해주는 이유는 같은 값을 갖는 블럭일 경우 값이 더해서 합쳐지기 때문이다.
• 만약 이동하지 않고 다음 위치가 그대로라도 현재위치를 먼저 0으로 초기화했으므로 더해주면 값은 똑같다. 
• 중요한건 현재위치를 먼저 0으로 초기화하고 다음에 갈 위치에 값을 더해주어야한다. 이거 순서 바뀌면 안됨.
• 자세한건 코드참조

 

# 주의할 점 

 

• 백트래킹 조건 생각하기 - map원복해주어야함
• 같은 값을 갖는 블럭 처리를 위해 boolean 배열 설정

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.StringTokenizer;

public class bj12100_2048Easy {
	static int N, map[][], ans = 0;
	static int dr[] = { -1, 1, 0, 0 };// 상하좌우
	static int dc[] = { 0, 0, -1, 1 };
	static boolean check[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dfs(0);
		System.out.println(ans);
	}

	private static void dfs(int idx) {
		if(idx == 5) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					ans = Math.max(ans, map[i][j]);
				}
			}
			return;
		}
		int origin[][] = new int[N][N];
		for(int i = 0; i < N; i++)
			origin[i] = map[i].clone();
		for (int d = 0; d < 4; d++) {
			move(map, d);
			dfs(idx+1);
			for (int i = 0; i < origin.length; i++) {
				map[i] = origin[i].clone();
			}
		}
	}

	private static void move(int map[][], int dir) {
		check = new boolean[N][N];
		if (dir == 0) {// 상
			for (int j = 0; j < N; j++) {
				for (int i = 0; i < N; i++) {
					if (map[i][j] != 0) {
						int num = map[i][j];
						Point next = go(i, j, dir, map);
						map[i][j] = 0;
						map[next.x][next.y] += num;
					}
				}
			}
		} else if (dir == 1) {// 하
			for (int j = 0; j < N; j++) {
				for (int i = N - 1; i >= 0; i--) {
					if (map[i][j] != 0) {
						int num = map[i][j];
						Point next = go(i, j, dir, map);
						map[i][j] = 0;
						map[next.x][next.y] += num;
					}
				}
			}
		} else if (dir == 2) {// 좌
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] != 0) {
						int num = map[i][j];
						Point next = go(i, j, dir, map);
						map[i][j] = 0;
						map[next.x][next.y] += num;
					}
				}
			}
		} else {// 우
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					if (map[i][j] != 0) {
						int num = map[i][j];
						Point next = go(i, j, dir, map);
						map[i][j] = 0;
						map[next.x][next.y] += num;
					}
				}
			}
		}
	}

	private static Point go(int i, int j, int d, int map[][]) {
		Point p = new Point();
		int r = i;
		int c = j;
		while (true) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			// 범위 밖, 0이 아니면서 내 값과 같지 않을때
			if (nr < 0 || nc < 0 || nr >= N || nc >= N || (map[nr][nc] != 0 && map[i][j] != map[nr][nc])) {
				p = new Point(r, c);
				break;
			}
			//같은 경우
			if(map[i][j] == map[nr][nc]) {
				if(check[nr][nc]) {
					p = new Point(r, c);
					break;
				}else {
					check[nr][nc] = true;
				}
			}
			r = nr;
			c = nc;
		}
		return p;
	}
}

 

 

 

REVIEW

5달 전에는 이거 10번 도전했는데 틀렸습니다만 주구장창 나와서 짜증나서 던졌던 문제다.

정답률도 25프로고.. 계속 미뤄뒀는데, 오늘 풀었을때 너무 쉽고 빠르게 풀렸다.

그때는 뭐가 문제였던거지....? 요즘 예전에 못 풀었던 문제를 풀때마다 희열을 느낀다!

이제 우울할때 어려운 문제 풀어야지,, 기분 매우 좋아지는중..