[백준] [삼성 SW 역량 테스트 기출 문제] 12100. 2048 (Easy)

🎮 2048 (Easy)

 

이 문제 별거 아닌거처럼 보였는데 이틀 걸렸다..

분명 맞는 것 같은데 뭐가 문제인지 몰라서 계속 쳐다만 보고 있다가

오늘 그냥 다 밀어버리고 차분하게 처음부터 생각하니

쉽게 풀렸다(? 😑

 

---

 

문제

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

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

 

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

 

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

 

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

 

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

 

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

 

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

 

입력

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

 

출력

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

---

🔑 IDEA

DFS와 Stack 자료구조를 이용하여 해결할 수 있었다.

 

 

void dfs(int depth)

• 최대 5번 이동할 수 있으므로 DFS의 depth가 5가 될 때를 base case로 설정한다.
• (depth != 5) 라면 for loop을 돌며 상,하,좌,우 중 한 방향을 선택할 수 있는데, 이 때 map의 배치가 바뀔 것을 대비해 tmpMap에 기존의 map의 상태를 저장해둔다.
• dfs 호출을 빠져나오면 map에 저장해둔 tmpMap을 덮어씌워 이전의 map 상태로 돌아간다. 

 

void move(int i)

• i 에 따라, 호출하는 메서드가 달라진다.
• 위로 이동할 때(i==0)는 moveUpward를, 아래로 이동할 때(i==1)는 moveDownward를, 
• 왼쪽으로 이동할 때(i==2)는 moveLeftward를, 오른쪽으로 이동할 때(i==3)는 moveRightward를 호출한다. 

 

void moveUpward()

move~ward() 메서드는 모두 같은 방식으로 구현되어있다. 그 중 moveUpward()를 예로 들어 동작을 설명하면 다음과 같다.

• 위로 이동하는 경우이므로, column 하나를 기준으로 처리한다. 
• 0번 컬럼을 처리하기 위해 stack을 하나 선언한다. 
• stack이 int[]를 저장하는 것은, operateStack()에서 설명한다.
• 이후 0번 컬럼의 원소들에 대해 operateStack()을 호출한다.
• operateStack()을 통해 만들어진 stack을 이용해 해당 컬럼을 갱신한다.  

 

void operateStack(int num, Stack<int[]> stack)

move~ward() 내부에서 operateStack(map[r][c], stack)이 호출되면 아래와 같이 처리된다. 

 

• stack은 길이 2짜리 int형 배열을 저장한다.
  • 이는 arr[0]에는 블럭의 숫자 값을, arr[1]에는 블럭이 합쳐진 것인지 여부를 저장하기 위함이다. 
  • arr[1]이 0이면 아직 합쳐지지 않은 블럭임을 의미하고, 1이면 합쳐진 블럭임을 의미한다.

• (stack != empty 이고 stack.peek의 값이 num과 같으며 아직 합쳐지지 않은 블럭이라면)
  • stack.pop() 한 뒤에  stack. push(num*2, 1)한다.

• 그렇지 않은 경우에는 stack.push(num, 0)한다.

 

💡  나의 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
	static int N;
	static int[][] map;
	static int max = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];

		for(int r=0; r<N; r++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int c=0; c<N; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}

		dfs(0);
		System.out.println(max);
	}

	private static void dfs(int depth) {
		//base case
		if(depth == 5) {
			findMax();
			return;
		}

		int[][] tmpMap = new int[N][N];
		copy(tmpMap, map); //현재 단계에서의 map 상태를 tmpMap에 저장해둔다.

		for(int i=0; i<4; i++) {
			move(i);
			dfs(depth+1);
			copy(map, tmpMap); //dfs를 빠져나온 후 이전의 map 상태로 다시 되돌린다.
		}
	}

	private static void move(int i) {
		switch(i) {
			case 0:
				moveUpward();
				break;
			case 1:
				moveDownward();
				break;
			case 2:
				moveLeftward();
				break;
			case 3:
				moveRightward();
				break;
		}
	}

	private static void operateStack(int num, Stack<int[]> stack) {
		//스택 맨 위 원소가 num과 같고, 아직 합쳐지지 않은 블럭이라면
		if(!stack.isEmpty() && stack.peek()[0] == num && stack.peek()[1] == 0) {
			stack.pop();
			stack.push(new int[] {num*2, 1});
			return;
		}
		stack.push(new int[] {num, 0});
	}

	private static void moveUpward() {
		for(int c=0; c<N; c++) {
			Stack<int[]> stack = new Stack<>(); //int[2] {숫자, 합쳐진 블럭인지 표시(0,1)}
			for(int r=0; r<N; r++) {
				if(map[r][c] == 0) continue;
				operateStack(map[r][c], stack);
			}

			for(int i=0; i<stack.size(); i++) {
				map[i][c] = stack.get(i)[0];
			}
			for(int i=stack.size(); i<N; i++) {
				map[i][c] = 0;
			}
		}
	}

	private static void moveDownward() {
		for(int c=0; c<N; c++) {
			Stack<int[]> stack = new Stack<>();
			for(int r=N-1; r>=0; r--) {
				if(map[r][c] == 0) continue;
				operateStack(map[r][c], stack);
			}

			for(int i=0; i<stack.size(); i++) {
				map[N-1-i][c] = stack.get(i)[0];
			}
			for(int i=0; i<N-stack.size(); i++) {
				map[i][c] = 0;
			}
		}
	}

	private static void moveLeftward() {
		for(int r=0; r<N; r++) {
			Stack<int[]> stack = new Stack<>();
			for (int c=0; c<N; c++) {
				if (map[r][c] == 0) continue;
				operateStack(map[r][c], stack);
			}

			for (int i=0; i<stack.size(); i++) {
				map[r][i] = stack.get(i)[0];
			}
			for (int i=stack.size(); i<N; i++) {
				map[r][i] = 0;
			}
		}
	}

	private static void moveRightward() {
		for(int r=0; r<N; r++) {
			Stack<int[]> stack = new Stack<>();
			for(int c=N-1; c>=0; c--) {
				if(map[r][c] == 0) continue;
				operateStack(map[r][c], stack);
			}

			for(int i=0; i<stack.size(); i++) {
				map[r][N-1-i] = stack.get(i)[0];
			}
			for(int i=0; i<N-stack.size(); i++) {
				map[r][i] = 0;
			}
		}
	}

	private static void findMax() {
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				max = Math.max(max, map[r][c]);
			}
		}
	}

	private static void copy(int[][] arr1, int[][] arr2) {
		for(int i=0; i<N; i++) {
			arr1[i] = arr2[i].clone();
		}
	}
}

 

 

---

 

 

12100번: 2048 (Easy)