[BOJ 12100] 2048 (Easy) (Java)

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

12100번: 2048 (Easy)

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

public class Main_BOJ_12100 {
	static int max=-1;
	static int[] dr= {-1,0,1,0};
	static int[] dc= {0,1,0,-1};
	static int N;
	static int[][] map;
	static int[][] temp;
	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];
		temp=new int[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());
				temp[i][j]=map[i][j];
			}
		}
		solve(0, new int[5]);
		System.out.println(max);
	}
	
	
	private static void solve(int cnt, int[] arr) {
		if (cnt==5) {
			for (int i=0; i<cnt; i++) {
				move(arr[i], new boolean[N][N]);
				check();
			}
			for (int i=0; i<N; i++) {
				map[i]=Arrays.copyOf(temp[i], N);
			}
			return;
		}
		for (int i=0; i<4; i++) {
			arr[cnt]=i;
			solve(cnt+1, arr);
		}
	}


	private static void check() {
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (max<map[i][j]) max=map[i][j];
			}
		}
		
	}

	public static void move(int d, boolean[][] check) {
		if (d==0) {
			for (int c=0; c<N; c++) {
				for (int r=0; r<N; r++) {
					if (map[r][c]!=0) play(r,c,d,check);
				}
			}
		}
		else if (d==1) {
			for (int r=0; r<N; r++) {
				for (int c=N-1; c>=0; c--) {
					if (map[r][c]!=0) play(r,c,d,check);
				}
			}
		}
		else if (d==2) {
			for (int c=0; c<N; c++) {
				for (int r=N-1; r>=0; r--) {
					if (map[r][c]!=0) play(r,c,d,check);
				}
			}
		}
		else if (d==3) {
			for (int r=0; r<N; r++) {
				for (int c=0; c<N; c++) {
					if (map[r][c]!=0) play(r,c,d,check);
				}
			}
		}
		
	}
	
	
	public static void play(int r, int c, int d, boolean[][] check) {
		int val, nr, nc;
		val=map[r][c];
		map[r][c]=0;
		nr=r+dr[d];
		nc=c+dc[d];
		boolean isCombine=false;
		while(true) {
			if (!isValid(nr,nc)) break;
			if (map[nr][nc]==0) {	//0일 경우 계속 이동
				nr+=dr[d];
				nc+=dc[d];
				continue;
			}
			if (map[nr][nc]==val && !check[nr][nc]) {	//합치는 경우
				check[nr][nc]=true;
				map[nr][nc]=val*2;
				isCombine=true;
				break;
			}		//그 외의 경우(다른 숫자 만나기 or 이미 합쳐진 애들 만나기)
			else break;
		}
		if (!isCombine) {
			map[nr-dr[d]][nc-dc[d]]=val;
		}
	}
	
	public static boolean isValid(int r, int c) {
		return r>=0 && c>=0 && r<N && c<N;
	}
	

}

시뮬레이션+dfs 문제.

 

우선 DFS 로 5번 돌려서 가능한 모든 경우의 수를 구한다.

한번 돌릴 때마다 최대값을 체크하는 함수를 호출해주어 답안을 갱신한다.

한 case 가 끝났을 때, 원본 배열값을 복사해서 원래 값으로 돌려줘야 한다.

 

한번 돌릴 때=>play 함수로 구현했다.

방향값 d를 받고, 쭉 움직여주면서 경계를 벗어나거나, 다른 숫자를 만나거나, 이미 합쳐진 애들 만날 때 탐색을 종료한다.

합치는 경우에는 map 값을 갱신하고 visit 배열에 방문 표시를 한 뒤 탐색을 종료한다.

합쳐지지 않았을 경우도 블록이 이동했을 수 있으므로 탐색 종료 조건을 만나기 직전으로 블록의 값을 옮겨주면 된다.

 

다른 분들의 코드를 보니(https://donggoolosori.github.io/2020/11/06/boj-12100/) 

, 이동할 때 for 문을 써서 이동할 수도 있었다. k값을 이용해서 방향에 따라 움직임을 달리 한다. 빈칸일때는 값을 swap 해줘서 이동시키고, 합칠 조건이 될 때는 map 값을 바꿔주고, 이외의 경우는 break 하는 방식이다.