코딩문제풀이/Baekjoon
[Java] 백준12100번 : 2048(Easy)
코딩하는 포메라니안
2022. 3. 30. 16:23
1. 문제
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
2. 풀이 과정
처음엔 쉬운 풀이 방법이 있을까 생각하다가, 안 떠올라서 그냥 모든 경우의 수를 다 돌려보고 생각해봐야겠다 하고 구현했는데, 통과가 되었다.
위로, 아래로, 왼쪽으로, 오른쪽으로 각각 0, 1, 2, 3으로 생각하고 5개를 뽑는 중복 순열을 만들었다. 선택한 차례대로 함수를 실행시켜 결과를 냈다.
1) 최대값 구하기
- 처음 값을 입력받을 때, 확인
- 두 값이 같아서 합칠 때, 확인
=> 두 경우만 고려하면 된다.
2) 네 방향 중 하나로 이동시키기
- 자신이 앞으로 갈 수 있는 위치 = prev
- 지금 보고 있는 위치 = j
단계 1) Up, Down, Left, Right를 따로 생성
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Boj12100 {
static int N, max;
static int order[], origin[][];
public static void permutation(int cnt) {
if(cnt==5) {
//배열 복사
int[][] carr = new int[N][N];
for(int i=0;i<N;i++)
carr[i] = origin[i].clone();
for(int i=0;i<5;i++) {
switch(order[i]) {
case 0:
goUp(carr);
break;
case 1:
goDown(carr);
break;
case 2:
goLeft(carr);
break;
case 3:
goRight(carr);
break;
}
}
return;
}
for(int i=0;i<4;i++) {//4방향 up, down, left, right
order[cnt]=i;
permutation(cnt+1);
}
}
public static void goUp(int arr[][]) {
for(int i=0;i<N;i++) {
int prev = 0;
for(int j=1;j<N;j++) {
if(arr[j][i]==0) {
continue;
}
else {
if(arr[prev][i]==0) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
else {
if(arr[prev][i] == arr[j][i]) {//값이 같으면
arr[prev][i]*=2;
arr[j][i] = 0;
max = Math.max(max, arr[prev][i]);
prev++;
}
else {
if(++prev != j) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
}
}
}
}
}
}
public static void goDown(int arr[][]) {
for(int i=0;i<N;i++) {
int prev = N-1;
for(int j=N-2;j>=0;j--) {
if(arr[j][i]==0) {
continue;
}
else {
if(arr[prev][i]==0) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
else {
if(arr[prev][i] == arr[j][i]) {//값이 같으면
arr[prev][i]*=2;
arr[j][i] = 0;
max = Math.max(max, arr[prev][i]);
prev--;
}
else {
if(--prev != j) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
}
}
}
}
}
}
public static void goLeft(int arr[][]) {
for(int i=0;i<N;i++) {
int prev = 0;
for(int j=1;j<N;j++) {
if(arr[i][j]==0) {
continue;
}
else {
if(arr[i][prev]==0) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
else {
if(arr[i][prev] == arr[i][j]) {//값이 같으면
arr[i][prev]*=2;
arr[i][j] = 0;
max = Math.max(max, arr[i][prev]);
prev++;
}
else {
if(++prev != j) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
}
}
}
}
}
}
public static void goRight(int arr[][]) {
for(int i=0;i<N;i++) {
int prev = N-1;
for(int j=N-2;j>=0;j--) {
if(arr[i][j]==0) {
continue;
}
else {
if(arr[i][prev]==0) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
else {
if(arr[i][prev] == arr[i][j]) {//값이 같으면
arr[i][prev]*=2;
arr[i][j] = 0;
max = Math.max(max, arr[i][prev]);
prev--;
}
else {
if(--prev != j) {
arr[i][prev] = arr[i][j];
arr[i][j] = 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());
origin = new int[N][N];
order = new int[5];//방향 5개 선택
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
origin[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, origin[i][j]);
}
}
permutation(0);
System.out.println(max);
}
}
단계 2) Up&Down과 Left&Right를 하나로 묶음
묶은 기준은 2차원 배열의 접근 방식이다 Up&Down은 모두 arr[i][j]로 한 열씩 탐색한다면,
Left&Right은 arr[j][i]로 한 행씩 차례로 탐색한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Boj12100_2 {
static int N, max;
static int order[], origin[][];
public static void permutation(int cnt) {
if(cnt==5) {
//배열 복사
int[][] carr = new int[N][N];
for(int i=0;i<N;i++)
carr[i] = origin[i].clone();
for(int i=0;i<5;i++)
move(order[i], carr);
return;
}
for(int i=0;i<4;i++) {//4방향 up, down, left, right
order[cnt]=i;
permutation(cnt+1);
}
}
public static void move(int n, int arr[][]) {
//up, down, left, right
int start = (n%2==0) ? 0 : N-1;
int inc = (n%2==0) ? 1 : -1;
if(n<2) {//up & down
for(int i=0;i<N;i++) {
int prev = start;
for(int j=start+inc; 0<=j && j<N; j+=inc) {
if(arr[j][i]==0) {
continue;
}
else {
if(arr[prev][i]==0) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
else {
if(arr[prev][i] == arr[j][i]) {//값이 같으면
arr[prev][i]*=2;
arr[j][i] = 0;
max = Math.max(max, arr[prev][i]);
prev+=inc;
}
else {
prev+=inc;
if(prev != j) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
}
}
}
}
}
}
else {//left & right
for(int i=0;i<N;i++) {
int prev = start;
for(int j=start+inc; 0<=j && j<N; j+=inc) {
if(arr[i][j]==0) {
continue;
}
else {
if(arr[i][prev]==0) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
else {
if(arr[i][prev] == arr[i][j]) {//값이 같으면
arr[i][prev]*=2;
arr[i][j] = 0;
max = Math.max(max, arr[i][prev]);
prev+=inc;
}
else {
prev += inc;
if(prev != j) {
arr[i][prev] = arr[i][j];
arr[i][j] = 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());
origin = new int[N][N];//벽세움
order = new int[5];//방향 5개 선택
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
origin[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, origin[i][j]);
}
}
permutation(0);
System.out.println(max);
}
}
