🔗문제 링크
🔒 문제 설명
4x4 크기의 보드 위에 있는 블록들을 4방향 중 하나로 이동시키는 게임이다. 이때 같은 값의 블록이 충돌하면 두 블록은 합쳐지며 값이 2배가 된다. 한번의 이동에서 한 블록은 한번만 합쳐질 수 있다.
-
예시 1) 그림 10에서 위로 블록들을 옮기면 그림 11이 된다.
-
예시 2) 아래 그림과 같이 이동하려는 방향에 있는 블록이 먼저 합쳐진다.
최대 5번 이동시켜서 얻을 수 있는 가장 큰 수를 출력하자
🧾 입력 예시
4
2 0 4 8
0 2 2 0
4 4 0 0
0 8 1 1첫번째 줄에는 보드의 크기 N이 주어진다.
두번째 줄부터 N개의 줄에는 보드위 블록의 정보가 주어진다.
🔎 출력 예시
16
🔑 문제 풀이
-
5번 움직이는 루트를 정하기 위하여 dfs()메소드를 활용하였다.
-
5번 이동할 방향이 정해졌으면 play()메소드에서 해당 방향으로 블록들을 움직인다.
2-1. 주어진 방향으로 모든 블록을 움직인다.(move())
2-2. 옮겨진 블록들 중 방향과 동일하게 인접한 블록들을 합쳐준다.(merge())
또한 merge되는 경우 ret값을 갱신해준다.2-3. 블록들이 합쳐지면 빈 칸이 생기므로 다시 한 번 옮겨준다(move())
-
2번으로 돌아가 다른 루트에 대하여 반복한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
Main z = new Main();
z.solution();
}
int N = 0;
int[][] map;
int ret = 0;
private void solution() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ret = Integer.MIN_VALUE;
N = Integer.parseInt(br.readLine());
map = 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());
ret = Math.max(ret, map[i][j]);
}
}
dfs(0,"");
System.out.println(ret);
}
int[][] dirs = {{-1,0},{0,-1},{1,0},{0,1}}; // 상 좌 하 우
private void dfs(int dep, String dir) {
if(dep==5) {
play(copyArr(),dir);
return;
}
for(int i=0 ; i<4 ; i++) {
dfs(dep+1,dir+i);
}
}
private void play(int[][]arr, String dirStr) {
for(int i=0 ; i<dirStr.length() ; i++) {
int dir = Integer.parseInt(dirStr.charAt(i)+"");
move(arr, dir);
merge(arr, dir);
move(arr, dir);
}
}
private void move(int[][]arr, int dir) {
if(dir<2) {
// 상 좌
for(int i=0 ; i<=N-1 ; i++) {
for(int j=0 ; j<=N-1; j++) {
int cRow = i;
int cCol = j;
int nRow = i + dirs[dir][0];
int nCol = j + dirs[dir][1];
while(inRange(nRow, nCol) && arr[nRow][nCol]==0) {
arr[nRow][nCol] = arr[cRow][cCol];
arr[cRow][cCol] = 0;
cRow = nRow;
cCol = nCol;
nRow = cRow + dirs[dir][0];
nCol = cCol + dirs[dir][1];
}
}
}
}else {
// 하 우
for(int i=N-1 ; i>=0 ; i--) {
for(int j=N-1 ; j>=0; j--) {
int cRow = i;
int cCol = j;
int nRow = i + dirs[dir][0];
int nCol = j + dirs[dir][1];
while(inRange(nRow, nCol) && arr[nRow][nCol]==0) {
arr[nRow][nCol] = arr[cRow][cCol];
arr[cRow][cCol] = 0;
cRow = nRow;
cCol = nCol;
nRow = cRow + dirs[dir][0];
nCol = cCol + dirs[dir][1];
}
}
}
}
}
private void merge(int[][]arr, int dir) {
switch (dir) {
case 0 : // 상
for(int j=0 ; j<N ; j++) {
for(int i=0 ; i<N ; i++) {
if(arr[i][j]==0)
continue;
int nRow = i + dirs[dir][0];
if(inRange(nRow,j) && arr[i][j]==arr[nRow][j]) {
arr[nRow][j] *= 2;
ret = Math.max(ret, arr[nRow][j]);
arr[i][j] = 0;
}
}
}
break;
case 1 : // 좌
for(int i=0 ; i<N ; i++) {
for(int j=0 ; j<N ; j++) {
if(arr[i][j]==0)
continue;
int nCol = j + dirs[dir][1];
if(inRange(i,nCol) && arr[i][j]==arr[i][nCol]) {
arr[i][nCol] *= 2;
ret = Math.max(ret, arr[i][nCol]);
arr[i][j] = 0;
}
}
}
break;
case 2 : // 하
for(int j=0 ; j<N ; j++) {
for(int i=N-1 ; i>=0 ; i--) {
if(arr[i][j]==0)
continue;
int nRow = i + dirs[dir][0];
if(inRange(nRow,j) && arr[i][j]==arr[nRow][j]) {
arr[nRow][j] *= 2;
ret = Math.max(ret, arr[nRow][j]);
arr[i][j] = 0;
}
}
}
break;
case 3 : // 우
for(int i=0 ; i<N ; i++) {
for(int j=N-1 ; j>=0 ; j--) {
if(arr[i][j]==0)
continue;
int nCol = j + dirs[dir][1];
if(inRange(i,nCol) && arr[i][j]==arr[i][nCol]) {
arr[i][nCol] *= 2;
ret = Math.max(ret, arr[i][nCol]);
arr[i][j] = 0;
}
}
}
break;
default:
break;
}
}
private boolean inRange(int row, int col) {
if(row>=0 && row<N && col>=0 && col<N)
return true;
return false;
}
private int[][] copyArr(){
int[][] cArr = new int[N][N];
for(int i=0 ; i<N ; i++) {
for(int j=0 ; j<N ; j++) {
cArr[i][j] = map[i][j];
}
}
return cArr;
}
}
📇 결과
