[백준]12100 2048 (Easy) (자바)
문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
입출력 예
풀이
모든 경우를 다 해본다.
각 라인을 이동시킬 때
1. 0이 아닌 원소를 큐에 offer
2. 다음 원소와 1의 원소가 같다면 다음 원소까지 offer 후 더한 값을 배열에 넣음
코드
import java.io.*;
import java.util.*;
public class Main_B12100 {
static int n,answer=0;
//5번 이동을 위한 dfs
static void dfs(int depth,int[][]arr) {
if(depth==5) {
answer=Math.max(answer, getMax(arr));
return;
}
for(int i=0;i<4;i++) {
dfs(depth+1,move(i,arr));
}
}
//각 배열의 최댓값 찾는 메서드
static int getMax(int[][]arr) {
int temp=0;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(arr[i][j]>temp)temp=arr[i][j];
}
}
return temp;
}
//한 라인씩 이동
static void lineMove(int[][]arr,Queue<Integer> q,int i,int d){
int[]temp=new int[n];
int num=0,index=0;
while(!q.isEmpty()) {
if(num==0)num=q.poll();
if(!q.isEmpty()&&num==q.peek()) {
q.poll();
temp[index++]=num*2;
}
else temp[index++]=num;
num=0;
}
//상
if(d==0)for(int k=0;k<n;k++)arr[k][i]=temp[k];
//하
else if(d==1)for(int k=0;k<n;k++)arr[n-k-1][i]=temp[k];
//좌
else if(d==2)for(int k=0;k<n;k++)arr[i][k]=temp[k];
//우
else for(int k=0;k<n;k++)arr[i][n-k-1]=temp[k];
}
//각 방향으로 배열 이동
static int[][] move(int d,int[][]arr) {
Queue<Integer> q = new LinkedList<>();
int[][]map=new int[n][n];
if(d==0) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(arr[j][i]!=0)q.offer(arr[j][i]);
}
lineMove(map,q,i,d);
}
}
else if(d==1) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(arr[n-j-1][i]!=0)q.offer(arr[n-j-1][i]);
}
lineMove(map,q,i,d);
}
}
else if(d==2) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(arr[i][j]!=0)q.offer(arr[i][j]);
}
lineMove(map,q,i,d);
}
}
else {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(arr[i][n-j-1]!=0)q.offer(arr[i][n-j-1]);
}
lineMove(map,q,i,d);
}
}
return map;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n=Integer.parseInt(br.readLine());
int[][]arr=new int[n][n];
for(int i=0;i<n;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<n;j++) {
arr[i][j]=Integer.parseInt(st.nextToken());
}
}
dfs(0, arr);
System.out.println(answer);
}
}
Author And Source
이 문제에 관하여([백준]12100 2048 (Easy) (자바)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jihun333/백준12100-2048-Easy-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)