[BOJ] 12100 2048(Easy) - Java

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

---

1. 문제 요약

2048게임의 규칙과 같다. 다른 점은 방향 이동 시 새로운 숫자가 추가되지 않는 것이다.

2. 풀이

dfs + 시뮬레이션 문제이다.

dfs를 사용해서 5회를 움직였을 때 발생하는 모든 경우를 본다.

4방향 모두 따져보는데,

1. save : 움직이기 전 map을 미리 복사해서 savemap에 저장해준다.

2. move : 숫자들을 움직인다. 움직여서 합쳐진 숫자들의 위치는 visited 처리를 해준다.

3. visitedInit : visited 처리를 모두 false로 초기화 시켜준다. (다음 움직일 때 합쳐질 숫자들을 위해)

4. restore : 5회 움직임이 끝나면 다른 방향으로도 봐야하므로 바로 전에 저장해둔 savemap을 불러와 map에 다시 붙여넣기 해준다.

 

내가 놓친 부분은

1) 움직인 다음에는 중복 합쳐짐을 막기 위해 체크한 visited를 초기화해서 다음 움직임에서도 숫자들이 합쳐질 수 있게 해줘야 한다.

  => 내가 놓친 부분은 이것을 dfs 이전에 해줘야 하는데 dfs 이후에 해준 점이다. 새로운 턴임에도 불구하고 초기화가 안된 것을 발견하였다.

2) 움직이는 방향마다 움직임을 시작하는 위치가 다르다. => 상(0,0) / 하(N-1,0) / 좌(0,0) / 우(0,N-1) 

  => 4방향 모두 (0,0)부터 움직이게 해서 문제가 되었다.

 

처음에는 움직인 숫자들을 원복해줄 때 List를 사용하려고 했다. 이렇게 하면 하나하나 움직인 방향, 움직인 좌표 등등을 생각해줘야 했기 때문에 풀면서 나도 헷갈렸고 내 코드를 본 친구도 헷갈려서 이해하기 어렵다고 했다.

copymap을 쓰는게 좋지않겠냐는 친구의 말에 시도해보았고 이해하기도 훨씬 쉬웠다.

map 원복이 필요하다면 copymap을 사용하는 방법을 생각해보자.

 

3. 코드

package a22_11_12;

import java.io.*;
import java.util.*;

public class BOJ_12100_2048Easy2 {

	static boolean[][] visited;
	static int[][] map;
	static int[][][] savemap;
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	static int N, ans;
	static Queue<Pos> queue = new ArrayDeque<> ();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		savemap = new int[5][N][N];
		visited = new boolean[N][N];
		
		for (int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(0);
		System.out.println(ans);
	}
	
	static void dfs(int cnt) {
		if (cnt == 5) {
			check();
			return;
		}
		
		for (int d=0; d<4; d++) {
			save(cnt, d);
			move(d, cnt);
			visitedInit();
			dfs(cnt+1);
			restore(cnt);
		}
	}
	
	static void save(int cnt, int d) {
		// savemap에  이동 전 map을 저장
		if (d == 0 || d==2) { // 상, 좌 : (0,0)시작
			for (int i=0; i<N; i++) {
				for (int j=0; j<N; j++) {
					savemap[cnt][i][j] = map[i][j];
					if (map[i][j] != 0) {
						queue.offer(new Pos(i, j, map[i][j]));
					}
				}
			}
		} else if (d==1) { // 하 : (N-1,0)시작
			for (int i=N-1; i>=0; i--) {
				for (int j=0; j<N; j++) {
					savemap[cnt][i][j] = map[i][j];
					if (map[i][j] != 0) {
						queue.offer(new Pos(i, j, map[i][j]));
					}
				}
			}
		} else if (d==3) { // 우 : (0,N-1)시작
			for (int i=0; i<N; i++) {
				for (int j=N-1; j>=0; j--) {
					savemap[cnt][i][j] = map[i][j];
					if (map[i][j] != 0) {
						queue.offer(new Pos(i, j, map[i][j]));
					}
				}
			}
		}
	}
	
	static void move(int d, int cnt) {
		
		while (!queue.isEmpty()) {
			Pos cur = queue.poll();
			int ny = cur.y;
			int nx = cur.x;
			int num = cur.num;
			
			while (true) {
				ny += dy[d];
				nx += dx[d];
				if (ny<0 || ny>=N || nx<0 || nx>=N) {
					ny-=dy[d];
					nx-=dx[d];
					break;
				}
				if (map[ny][nx] != 0) break;				
			} //ny, nx가 정해짐
			
			if (!(cur.y == ny && cur.x == nx)) {
				if (map[ny][nx] == 0) {
					map[cur.y][cur.x] = 0;
					map[ny][nx] = num;
				} else if (map[ny][nx] == num) {
					
					if (visited[ny][nx] == false && visited[cur.y][cur.x] == false) { //처음 합쳐짐
						map[cur.y][cur.x] = 0;
						map[ny][nx] = num+num;
						visited[ny][nx] = true;
					} else { //이전에 이미 합쳐짐
						map[cur.y][cur.x] = 0;
						ny-=dy[d];
						nx-=dx[d];
						map[ny][nx] = num;
					}
					
				} else if (map[ny][nx] != num) {
					map[cur.y][cur.x] = 0;
					ny-=dy[d];
					nx-=dx[d];
					map[ny][nx] = num;
				}
			}
		}
	}
	
	static void restore(int cnt) {
		//이동 한 map에  이전에 저장한 savemap을 다시 복사
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = savemap[cnt][i][j];
			}
		}
	}
	
	static void visitedInit() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				visited[i][j] = false;
			}
		}
	}
	
	static void check() {
		int max = 0;
		for (int i=0; i<N; i++) {
			for (int j = 0; j<N; j++) {
				max = Math.max(max, map[i][j]);
			}
		}
		ans = Math.max(max, ans);
	}
	
	static class Pos {
		int y, x, num;
		Pos(int y, int x, int num) {
			this.y = y;
			this.x = x;
			this.num = num;
		}
	}
}

 

4. 사담

이거 푸는데 3일 걸렸다 난 대체 언제 느는걸까? 제발 늘고있는 중이길 ^_ㅠ

코테에 나오면 그 자리에서 바로 풀 수 있을까..?