[백준 12100] 2048 Easy 새로운 풀이

문제 설명

문제 링크

코드 리뷰

이전에 풀었던 문제였는데, 다시 풀어보게 되었다.

동서남북 방향에 대한 코드의 90퍼센트 이상이 중복되는 코드였고, 이런 경우 코드가 길어지고 디버깅을 할 경우 오래걸릴 수 있다.

이번에는 동서남북에 대한 각각의 코드를 하나의 코드로 해결할 수 있는 방법으로 해결하였다.

삼성 코딩테스트 문제 유형들을 보면 이렇게 코드의 중복이 발생하는 문제들이 많다.

이런 경우, 중복을 하나의 코드(함수)로 작성하여 푸는 방법에 대한 연습을 앞으로도 많이 해야겠다.

본론으로 들어가면, 만약 오른쪽으로 이동시키는 경우, 각 행마다 가장 오른쪽에 있는 칸부터 검색을 시작하게 구현한다.

그리고, 선택된 칸을 오른쪽으로 보낼 수 있는 만큼 보낸다. 그 때 합쳐질 수 있는 경우라면 합치고 아니면 이동만 시키게 구현하였다. 코드에 주석을 달았다.

또한, 5개의 이동방향을 다 뽑고 난 후에 시뮬레이션을 시작하지 않고, 백트래킹을 통해 한 방향이 선택되면 미리 이동 시켜놔서 똑같은 연산의 반복을 줄였다.

import java.io.*;
import java.util.*;
public class BOJ12100_2048Easy {
	static int N,ans;
	static int[][] bd;
	static boolean[][] check;
	static int[] dc = {0,0,-1,1};
	static int[] dr = {-1,1,0,0};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		bd = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				bd[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		rep_permu(0);
		System.out.println(ans);
	}
	static void rep_permu(int r) {
		if(r==5) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(bd[i][j]!=0) {
						ans = Math.max(ans, bd[i][j]);
					}
				}
			}
			return;
		}
		int[][] tmp = new int[N][N];
		copy(tmp,bd); //배열을 미리 복사시켜 둔다.
		for(int idx=0; idx<4; idx++) {
			solve(idx); //백트래킹
			rep_permu(r+1);
			copy(bd,tmp); //다시 사용
		}
	}
	static void solve(int op) {
		check = new boolean[N][N];
		int n=0,m=0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
                //op 값이 0 : left, 1 : right, 2 : up, 3 : down
				if(op==0||op==2) {n=i; m=j;}
				else if(op==1) {n=i; m=N-1-j;}
				else {n=N-1-i; m=j;} //이동 방향에 맞게 n과 m설정
				if(bd[n][m]==0 || check[n][m]) continue;
				int num = bd[n][m];
				bd[n][m]=0;
				int nn = n+dc[op];
				int nm = m+dr[op];
				while(inner(nn,nm)&&bd[nn][nm]==0) {//이동할 수 있는 만큼 이동
					n=nn; m=nm;
					nn+=dc[op]; nm+=dr[op];
				}
				if(inner(nn,nm)&& bd[nn][nm]==num && !check[nn][nm]) {//합칠 경우에 합침
					bd[nn][nm]=2*num;
					check[nn][nm]=true;
				}else {//못합치는 경우 이동한 곳에 값 저장
					bd[n][m]=num;
				}
			}
		}
	}
	static void copy(int[][] arr1, int[][] arr2) {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				arr1[i][j]=arr2[i][j];
			}
		}
	}
	static boolean inner(int n, int m) {
		return 0<=n && n<N && 0<=m && m<N;
	}
}