[백준 12100번] 2048(easy) - java

문제 설명

1. N개의 크기가 정해진 보드가 주어진다.

2. 보드에 2~ 1024의 크기 내의 숫자들이 주어진다.

3. 숫자들은 위로, 아래로, 왼쪽으로, 오른쪽으로 딱 붙여서 정리할 수 있으며, 위로 이동하는 경우 이전의 숫자와 이후의 숫자가 같으면 두 숫자는 합쳐진다( 8에 8이 이동하면 16하나가 되는 느낌이다.)

4. 5번의 이동이 있은 후 가능한 최대 숫자를 return하면 된다.

풀이 과정

 1. 엄청나게 코드를 더럽게 풀었다. 모든 경우를 하나하나 만들었음...

 2. 재귀함수 문제이다. 적절한 범위를 지정해 주면 된다.

 3. 간단하게 코드에 대해 설명하자면

- 위, 아래, 오른, 왼 코드를 하나씩 만들어서 모든 경우를 탐색한다 (위 - 위 - 위 - 위 - 위), (위, 위, 위, 위, 아래) ......

- 그리고 각각의 경우에서는 기존 보드를 가져와서 한쪽 면에 빈 칸 없이 딱 붙이는 방법을 정의한다 -> 맨위로 다 붙이려면 stack을 써서 0인 경우는 넣지 않고 이외의 경우 집어넣은 후 그 stack을 위에서부터 넣으면 될 것이다.

- 그럼 그 stack에서 같은 숫자들을 합치는 경우는, stack의 맨 위 값과 이후 0이외의 숫자의 값이 같으면, 그걸 2배 해주면 된다. 

--- 참고로 4 4 4 8 처럼 4와4를 더해 8이 되고, 8과8을 더해 16이 되는 경우라고 하면 4와4만 해주고 이후 8은 더하면 안될 것이다. 그 경우는 한번 합치면 이를 boolean으로 표시해주고 진행해주면 될 것이다.

- 그렇게 해서 stack에 값이 들어가면, 이후 다시 처음부터 위의 프로세스들을 진행시킬 새로운 맵을 만들어 줄 것이다. 이는 stack에 있는 것들을 뒤에서부터 넣으면 가능할 것이다.

- 그리고 이렇게 stack의 값들을 뺴줄 때 마다 최대값을 구해준다.

- 그걸 총 5번 반복한 뒤 나가면 최대의 숫자를 return할 수 있다.

 

이렇게 적혀져 있으면 뭔소린지 잘 이해가 안갈것이다... 아무래도 코드가 많이 더러우니 주석으로 설명을 해 넣겠다.

코드

	import java.util.*;
	public class Main {
	public static int ans = 2; // 보드들의 최소값은 2이다.
	public static int N;
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	// 보드 입력단.
	N = sc.nextInt();
	int map[][] = new int[N][N];
	for(int i=0; i<N; i++) {
	for(int j=0; j<N; j++) {
	map[i][j] = sc.nextInt();
	}
	}
	// 위 아래 양옆의 모든 경우를 시작해 준다.
	up(map, 0);
	down(map, 0);
	left(map, 0);;
	right(map, 0);
	System.out.println(ans);
	}
	public static void up(int map[][], int nowCnt) { // 이전에 만들어진 map과 지금까지 진행한 숫자 nowCnt
	int nowMap[][] = new int[N][N]; // 이번 함수를 통해 만들 nowMap
	boolean once = false; // 한 번 값이 합쳐지면 그렇게 만들어진 값은 다시 합쳐지면 안된다.
	for(int j=0; j<N; j++) { // 이게 중요한데, 위에서부터 하는 것이므로 i와 j가 반대로 될 것이다. 아래, 오른쪽, 왼쪽은 이와같이 생각하면 된다.
	Stack<Integer> filter = new Stack<>(); // 빈 칸을 없애기 위해 사용할 filter
	for(int i=0; i<N; i++) {
	if(map[i][j]!=0) // 빈 칸이면 걍 무시하고 지나가버리기~
	if(filter.isEmpty()) { // filter가 비었으면 당연히 하나는 넣어줘야한다.
	filter.add(map[i][j]);
	once = false; // 첫값이면 무조건 위의숫자랑 더해졌을리가 없다.
	}else {
	if(filter.peek()==map[i][j] && !once) { // 앞의 과정에서 들어간 값과 이제 비교할 숫자가 같은경우, 또 앞의 과정에서 들어간 값이 이미 한번 더해진 경우가 아닌 경우
	int before = filter.pop();
	filter.add(before*2); // 숫자를 2배 해준다.
	once = true; // 이렇게 stack의 맨 위에 들어간 숫자는 또 더해져서는 안된다.
	continue;
	}else { // 둘의 숫자가 다르거나, 이미 한번 더해준 숫자인 경우는 그냥 다음 숫자를 넣어주면 된다.
	filter.add(map[i][j]);
	once = false; // 이 값은 더해진 것이 아니므로 다시 false
	}
	}
	}
	while(!filter.isEmpty()) { // 그렇게 해당하는 줄의 숫자들을 완성했으면 빈칸 없이 넣어준다.
	int num = filter.pop(); // 하나 꺼냄
	ans = Math.max(ans, num); // 그리고 만들어진 숫자들 중 최대값을 저장한다
	nowMap[filter.size()][j] = num; // 보면 제일먼저 만든숫자가 맨 나중에 나오고, 가장 최근에 만들어진 숫자가 처음 나온다. 그리고 가장 먼저 만든 숫자는 맨 위로 가야하고 그러면 거꾸로 하면 된다.
	}
	}
	// 5번 하는 경우들을 전체 검색
	nowCnt++;
	if(checkCnt(nowCnt)) {
	return;
	}
	up(nowMap, nowCnt);
	down(nowMap, nowCnt);
	left(nowMap, nowCnt);
	right(nowMap, nowCnt);
	}
	// 아래도 이와 비슷한 로직이다.
	public static void down(int map[][], int nowCnt) {
	int nowMap[][] = new int[N][N];
	boolean once = false;
	for(int j=0; j<N; j++) {
	Stack<Integer> filter = new Stack<>();
	for(int i=N-1; i>=0; i--) {
	if(map[i][j]!=0) {
	if(filter.isEmpty()) {
	filter.add(map[i][j]);
	once = false;
	}else {
	if(filter.peek()==map[i][j] && !once) {
	int before = filter.pop();
	filter.add(before*2);
	once = true;
	continue;
	}else {
	filter.add(map[i][j]);
	once = false;
	}
	}
	}
	}
	while(!filter.isEmpty()) {
	int num = filter.pop();
	ans = Math.max(ans, num);
	nowMap[filter.size()][j] = num;
	}
	}
	nowCnt++;
	if(checkCnt(nowCnt)) {
	return;
	}
	up(nowMap, nowCnt);
	down(nowMap, nowCnt);
	left(nowMap, nowCnt);
	right(nowMap, nowCnt);
	}
	public static void left(int map[][], int nowCnt) {
	int nowMap[][] = new int[N][N];
	boolean once = false;
	for(int i=0; i<N; i++) {
	Stack<Integer> filter = new Stack<>();
	for(int j=0; j<N; j++) {
	if(map[i][j]!=0) {
	if(filter.isEmpty()) {
	filter.add(map[i][j]);
	once = false;
	}else {
	if(filter.peek()==map[i][j] && !once) {
	int before = filter.pop();
	filter.add(before*2);
	once = true;
	continue;
	}else {
	filter.add(map[i][j]);
	once = false;
	}
	}
	}
	}
	while(!filter.isEmpty()) {
	int num = filter.pop();
	ans = Math.max(ans, num);
	nowMap[i][filter.size()] = num;
	}
	}
	nowCnt++;
	if(checkCnt(nowCnt)) {
	return;
	}
	up(nowMap, nowCnt);
	down(nowMap, nowCnt);
	left(nowMap, nowCnt);
	right(nowMap, nowCnt);
	}
	public static void right(int map[][], int nowCnt) {
	int nowMap[][] = new int[N][N];
	boolean once = false;
	for(int i=0; i<N; i++) {
	Stack<Integer> filter = new Stack<>();
	for(int j=N-1; j>=0; j--) {
	if(map[i][j]!=0) {
	if(filter.isEmpty()) {
	filter.add(map[i][j]);
	once = false;
	}else {
	if(filter.peek()==map[i][j] && !once) {
	int before = filter.pop();
	filter.add(before*2);
	once = true;
	continue;
	}else {
	filter.add(map[i][j]);
	once = false;
	}
	}
	}
	}
	while(!filter.isEmpty()) {
	int num = filter.pop();
	ans = Math.max(ans, num);
	nowMap[i][filter.size()] = num;
	}
	}
	nowCnt++;
	if(checkCnt(nowCnt)) {
	return;
	}
	up(nowMap, nowCnt);
	down(nowMap, nowCnt);
	left(nowMap, nowCnt);
	right(nowMap, nowCnt);
	}
	public static boolean checkCnt(int cnt) {
	if(cnt==5) return true;
	return false;
	}
	}

view raw 2048(easy) hosted with ❤ by GitHub