[BJ]BJ G2 12100 2048(Easy)

BJ G2 12100 2048(Easy)

 

 

문제링크

12100번: 2048 (Easy) (acmicpc.net)

12100번: 2048 (Easy)

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ G2 12100 2048(Easy) (naver.com)

BJ G2 12100 2048(Easy)

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2021. 10. 4.
 * @see https://www.acmicpc.net/problem/12100
 * @performance 16180	116
 * @category #시뮬레이션, #완탐
 * @memo
 * 탐색의 회수가 지극히 제한적 --> 구지 방문체크할 필요가 없을듯. 오히려 더 부담.
 */

public class BJ_G2_12100_2048_Easy {

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	static int N, MAX;
	static int [][] map;
	static int [][] deltas = {{-1, 0},{1, 0},{0, -1},{0, 1}};

	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		map = new int [N][N];
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<N; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
				MAX = Math.max(MAX, map[r][c]);
			}
		}// 입력 완료
		dfs(map, 0);
		System.out.println(MAX);
	}
	
	private static void dfs(int [][] map, int turn) {
		if(turn==5) {
			return;
		}
		
		for(int d=0; d<deltas.length; d++) {
			int [][] moved = move(map, d);
			dfs(moved, turn+1);
		}
	}
	
	/**
	 * 주어진 배열 map을 d 방향으로 이동 시킨 결과를 이차원 배열 형태로 반환한다.
	 * 이동 방향에 따라 먼저 점검해야 하는 부분이 달라진다.
	 * @param map
	 * @param d
	 * @return
	 */
	private static int [][] move(int [][] map, int d){
		int [][] newMap = new int [N][N];
		if(d==0) { // {-1, 0} --> 위로 이동 --> 위에서 아래로 탐색
			for(int c=0; c<N; c++) {
				int nextIdx = 0, baseBlock = -1;
				for(int r=0; r<N; r++) {
					// map[r][c]==0이면 할 일이 없다.. 다음으로~~
					if(map[r][c]==0) {
						continue;
					}
					if(map[r][c]==baseBlock) {
						newMap[nextIdx-1][c] <<=1;
						baseBlock=-1;
						MAX = Math.max(MAX, newMap[nextIdx-1][c]);
					}else {
						newMap[nextIdx++][c] =baseBlock = map[r][c];
					}
				}
			}
			
		}else if(d==1) { // {1, 0} --> 아래로 이동 --> 아래에서 위로 탐색
			for(int c=0; c<N; c++) {
				int nextIdx = N-1, baseBlock = -1;
				for(int r=N-1; r>=0; r--) {
					// map[r][c]==0이면 할 일이 없다.. 다음으로~~
					if(map[r][c]==0) {
						continue;
					}
					if(map[r][c]==baseBlock) {
						newMap[nextIdx+1][c]  <<=1;
						baseBlock=-1;
						MAX = Math.max(MAX, newMap[nextIdx+1][c]);
					}else {
						newMap[nextIdx--][c] =baseBlock = map[r][c];
					}
				}
			}
		}else if(d==2) { // {0, -1} --> 왼쪽으로 이동 --> 왼쪽에서 오른쪽으로 탐색
			for(int r=0; r<N; r++) {
				int nextIdx = 0, baseBlock = -1;
				for(int c=0; c<N; c++) {
					// map[r][c]==0이면 할 일이 없다.. 다음으로~~
					if(map[r][c]==0) {
						continue;
					}
					if(map[r][c]==baseBlock) {
						newMap[r][nextIdx-1]  <<=1;
						baseBlock=-1;
						MAX = Math.max(MAX, newMap[r][nextIdx-1]);
					}else {
						newMap[r][nextIdx++] =baseBlock = map[r][c];
					}
				}
			}
			
		}else { // {0, 1} --> 오른쪽으로 이동 --> 오른쪽에서 왼쪽으로 탐색
			for(int r=0; r<N; r++) {
				int nextIdx =N-1, baseBlock = -1;
				for(int c=N-1; c>=0; c--) {
					// map[r][c]==0이면 할 일이 없다.. 다음으로~~
					if(map[r][c]==0) {
						continue;
					}
					if(map[r][c]==baseBlock) {
						newMap[r][nextIdx+1]  <<=1;
						baseBlock=-1;
						MAX = Math.max(MAX, newMap[r][nextIdx+1]);
					}else {
						newMap[r][nextIdx--] =baseBlock = map[r][c];
					}
				}
			}
		}
		return newMap;
	}

	// REMOVE_START
	private static String src = "3\n"
								+ "2 2 4\n"
								+ "0 0 0\n"
								+ "0 0 0";
	// REMOVE_END

}