[백준 스터디 2주차] 12100 2048 (Easy) 골드2 - 자바(Java) / DFS / 시뮬레이션

📑 문제

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

12100번: 2048 (Easy)

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다. 

이하생략 ...

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

 

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

 

 

 

 

 

 

 

✒️ 풀이

 큰 그림을 그려보자면 아래와 같이 나눌 수 있다.

◻️ 이동횟수를 깊이로 하여, 각 단계마다 (위/아래/좌/우)를 택하는 DFS 탐색을 한다.

◻️ 택한 방향대로 블록들을 옮겨준 다음, 다음 단계로 넘어간다.

◻️ 5단계까지 왔으면, 만들어진 2048 블록 중 가장 큰 숫자를 찾아 결과값을 업데이트 해준다. 

◻️ 모든 DFS 탐색이 끝나고 결과값을 출력한다.

 

 

💡 이 사이에서 중요하게 체크해야 하는 부분은 이렇다.

✔️ DFS 탐색시 깊이 K에서 특정 방향으로 블록을 이동시킨 후 깊이 K+1로 넘어갔다면, 다시 K단계에서 다른 방향으로 이동시킬 경우를 생각하여 배열을 원래대로 돌려줘야 한다.

 

✔️ 블록을 이동시킬 때 발견한 블록을 옮길 위치(이전 칸)에 따라 세 가지의 케이스가 존재한다.

◻️ 이전 칸이 빈 곳이면

 그 위치로 블록을 옮겨준다. 단, 그 다음 블록이 지금 블록과 같은 숫자일 수도 있으니 이전 칸의 인덱스는 그대로 둔다. 즉, 다음 루프에서 이전 칸이 가르키는 것은 방금 옮긴 블록이 된다.

 

◻️ 이전 칸에 지금 블록과 같은 블록이 있으면

 숫자를 합쳐야 하는 케이스이다. 두 블록이 합쳐졌다는 의미로 이전 칸의 블록 숫자를 두 배로 바꿔주고, 현재 칸은 비워준 다음, 이전 칸을 가르키는 인덱스는 하나를 증가시킨다. 예를 들어 왼쪽 방향으로 합칠 시 (이전 칸, 현재 칸, 다음 칸)이 (4, 4, 8)로 있을 때, 결과가 (8, 8)이 되지 않고 (16)으로 몽땅 합쳐지는 경우를 막기 위함이다.

 

◻️ 이전 칸에 지금 블록과 다른 블록이 있으면

이전 칸은 더 이상 볼 필요가 없는 칸이 된다. 따라서 이전 칸을 가르키는 인덱스를 하나 증가시킨 다음 그 위치로 지금 블록을 옮긴 후 지금 자리를 비워준다. 단, 지금 자리를 비울 때에는 블록의 위치가 옮겨지지 않는 경우인지 체크가 필요하다. 

 

 

 

 

 

🙋‍♀️ 의견

 골드 2 이상 되면 진짜.................어마어마하게 상황을 생각하고 케이스를 나누고 세심하게 코드를 짜야하는 것 같다.

 디버깅하는데 시간이 많이 걸렸는데(print하는 함수도 따로 짜고), 풀고 나니까 뿌듯하네.

 

 아쉬운 점은.....케이스마다 코드는 비슷해서 변수만 바꿔주고 재활용하는 코드 하나로 딱 합칠 수 있을 듯 한 것? 아직 내 깜냥이 거기까지 안되는 것도 있고, 스터디 시간에 쫓기느라 그냥 여기서 끝냈다... 😭

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

/** https://www.acmicpc.net/problem/12100 */
public class Main_백준_12100_2048_골드2 {

	static int N, result=-1;
	static int[][] map;
	
	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 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());
			}
		}//input
		
		dfs(0);
		
		System.out.println(result);	
	}//end of main
	
	private static void dfs(int cnt) {
		if(cnt==5) {
			result = Math.max(result, getMaxNum(map));
			return;
		}
		
		// temp: cnt단계의 초기 map배열 상태를 저장해두기 위함
		int[][] temp = new int[N][N];
		copyArray(temp, map);// temp<-map
		
		for (int i = 0; i < 4; i++) {
			switch(i) {
				case 0:
					up(map);
					break;
				case 1:
					down(map);
					break;
				case 2:
					left(map);
					break;
				case 3:
					right(map);
					break;
			}
			dfs(cnt+1);
			copyArray(map, temp);// map<-temp
		}
		
	}//end of dfs
	
	private static void print(int[][] map) {
		for (int i = 0; i < N; i++) {
			System.out.println(Arrays.toString(map[i]));
		}
		System.out.println("===================================");
	}//end of print
	
	private static void copyArray(int[][] to, int[][] from) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				to[i][j] = from[i][j];
			}
		}
	}//end of copyArray
	
	private static int getMaxNum(int[][] map) {
		int max = map[0][0];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				max = Math.max(max, map[i][j]);
			}
		}
		return max;
	}//end of getMaxNum
	
	private static void up(int[][] map) {
		for (int i = 0; i < N; i++) { //0~N-1열
			int idx = 0;
			for (int j = 1; j < N; j++) { //1~N-1행
				int before = map[idx][i];
				int now = map[j][i];
				
				if(now!=0) {
					// 이전 칸이 빈 곳이면 그 곳으로 당겨간다
					if(before==0) {
						map[idx][i] = now;
						map[j][i] = 0;
					}
					// 이전 칸에 숫자가 있고, 그 숫자가 지금 칸과 같으면
					else if(before==now) {
						map[idx][i] *= 2;
						map[j][i] = 0;
						idx ++;
					}
					// 이전 칸에 숫자가 있지만 지금 칸과 다르면
					else {
						idx ++;
						map[idx][i] = map[j][i];
						if(idx!=j) map[j][i] = 0;
					}
				}
			}
		}
	}//end of up
	
	private static void down(int[][] map) {
		for (int i = 0; i < N; i++) { //0~N-1열
			int idx = N-1;
			for (int j = N-2; j >= 0; j--) { //1~N-1행
				int before = map[idx][i];
				int now = map[j][i];
				
				if(now!=0) {
					// 이전 칸이 빈 곳이면 그 곳으로 당겨간다
					if(before==0) {
						map[idx][i] = now;
						map[j][i] = 0;
					}
					// 이전 칸에 숫자가 있고, 그 숫자가 지금 칸과 같으면
					else if(before==map[j][i]) {
						map[idx][i] *= 2;
						map[j][i] = 0;
						idx --;
					}
					// 이전 칸에 숫자가 있지만 지금 칸과 다르면
					else {
						idx --;
						map[idx][i] = map[j][i];
						if(idx!=j) map[j][i] = 0;
					}
				}
			}
		}
	}//end of down
	
	private static void left(int[][] map) {
		
		for (int i = 0; i < N; i++) { //0~N-1행
			int idx = 0;
			for (int j = 1; j < N; j++) { //1~N-1열
				int before = map[i][idx];
				int now = map[i][j];
				
				if(now!=0) {
					// 이전 칸이 빈 곳이면 그 곳으로 당겨간다
					if(before==0) {
						map[i][idx] = now;
						map[i][j] = 0;
					}
					// 이전 칸에 숫자가 있고, 그 숫자가 지금 칸과 같으면
					else if(before==map[i][j]) {
						map[i][idx] *= 2;
						map[i][j] = 0;
						idx ++;
					}
					// 이전 칸에 숫자가 있지만 지금 칸과 다르면
					else {
						idx ++;
						map[i][idx] = map[i][j];
						if(idx!=j) map[i][j] = 0;
					}
				}
			}
		}
	}//end of left
	
	private static void right(int[][] map) {
		
		for (int i = 0; i < N; i++) { //0~N-1행
			int idx = N-1;
			for (int j = N-2; j >= 0; j--) { //1~N-1열
				int before = map[i][idx];
				int now = map[i][j];
				
				if(now!=0) {
					// 이전 칸이 빈 곳이면 그 곳으로 당겨간다
					if(before==0) {
						map[i][idx] = now;
						map[i][j] = 0;
					}
					// 이전 칸에 숫자가 있고, 그 숫자가 지금 칸과 같으면
					else if(before==map[i][j]) {
						map[i][idx] *= 2;
						map[i][j] = 0;
						idx --;
					}
					// 이전 칸에 숫자가 있지만 지금 칸과 다르면
					else {
						idx --;
						map[i][idx] = map[i][j];
						if(idx!=j) map[i][j] = 0;
					}
				}
			}
		}
	}//end of right
	
}//end of class​

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨