[백준 온라인 저지(BOJ)] 12100 2048(Easy) 자바 풀이 (arraylist와 배열을 이용한 두 가지 풀이)

BOJ 12100번 2048(Easy) 문제 자바(java) 풀이

• 랭크 : 골드2
• 백준 온라인 저지(BOJ) 12100번 2048(Easy) 문제 자바 풀이
• 백준 12100번 2048(Easy)

문제정리

이는 2048 게임을 직접 해보는 것이 더 빠르게 이해할 수 있을 것 같습니다.
간단히 이야기 하자면 2의 배수로만 이루어진 타일들이 있는데
같은 숫자의 타일이 겹쳐지면 더해지는 게임이며 최종적으로 2048이라는 숫자를 가지는 타일을 만들면 끝나는 게임입니다.
2048게임 해보기

문제풀이 첫 번째 (ArrayList, 중복순열 이용)

ArrayList를 중첩하여 이용하여 2차원 배열처럼 사용하여 게임판을 표현 하였습니다.
전체적인 로직은 다음과 같습니다.

우선 ArrayList를 중첩하여 2차원 배열 처럼 사용할 수 있도록 초기화 합니다(initList)
그 다음 move 함수를 통해 움직입니다.
이때 방향에 따라 switch문을 통해 나누었습니다.
제가 생각하는 이 문제의 핵심은 오른쪽==위로, 왼쪽==아래로 라는 것입니다.
오른쪽으로 이동하는 로직이랑 위로 이동시키는 로직이 같습니다.
위로 이동시킨다면 시계방향으로 맵을 회전 시켜서 오른쪽으로 이동시키는 것과 같습니다.

이를 이용하여 위나 아래로 이동하는 경우 list를 시계방향으로 뒤집고 로직을 수행한다음
다시 반시계 방향으로 뒤집어 원래대로 돌려주었습니다.

이를 중복순열을 통해 모든 경우를 체크해줍니다.
4개(0,1,2,3)중 4개를 고르는 중복순열을 고르고 나머지 하나는 0,1,2,3을 순회하며
0,1,2,3을 이용한 5가지의 모든 경우의 수를 계산합니다.

• 주의 할 점
  한 가지의 경우의 수가 끝날 때마다 백업해두었던 초기 배열을 가져와 다시 그 경우의 수에 맞게 이동시킨다.

• 최대 5번의 이동
  5번 이동 후의 최댓값을 구하는 것이 아니다. 1~5번 이동했을때의 최대값과 비교해야 한다.

오른쪽으로 이동 로직

왼쪽과 오른쪽으로 이동의 로직은 같기 때문에 오른쪽으로 이동할때를 기준으로 설명 드리겠습니다.
삽질을 많이 하다가 존재하는 0을 모두 제거하고 오른쪽에서 왼쪽으로 index를 이동하면서 확인한다면 된다는 것을 알게되었습니다.

1. 첫 행에 숫자가 0202와 같이 있다면 0을 제거합니다(22로 변함)
2. 그 다음 오른쪽에서 왼쪽으로 이동하며 같은 숫자인지 확인합니다.
3. 같은 숫자이면 값을 2배로 해주고 하나를 제거 합니다.
4. 그리고 게임판의 크기 만큼 나머지를 0으로 채워줍니다. 오른쪽으로 이동이니 왼쪽에 0을 채웁니다(0004가 됨)

가지치기

1. 이동해도 같은 경우
   중복순열로 모든 경우를 구하기에는 양이 꽤 많다. 그래서 가지치기를 해야해요
   한 번 이동후 다음에 다시 이동했는데 변화가 없을 경우에는 더 이상 이동하지 않도록 하면
   많은 경우의 수를 줄일 수 있습니다.

2. 이동 시 최댓값(branch에서의 최댓값)
   이 경우는 이 2048(easy) 문제 에서는 해주지 않아도 충분히 통과할 수 있습니다.
   하지만 2048(hard) 문제의 경우에는 이 가지치기도 해주어야 통과할 수 있습니다.
   이게 무슨 뜻이냐면 5번 이동하는 경우의 수가 여러가지가 있을 수 있겠죠??
   어떤 방법으로 5번을 모두 이동했다고 합시다. 이때의 최대값이 512라면 이와 같거나 더 큰 최대값을 갖기 위해서는
   이 전(4번 이동했을 경우)의 최대값이 최소 256이어야 합니다. 그래야 다음 이동으로 숫자가 합쳐져서 512가 될 테니까요
   branch_max[5] = 512
   branch_max[4] = 256
   branch_max[3] = 128
   branch_max[2] = 64
   branch_max[1] = 32
   이런 식으로 만들어 줍니다.
   그래서 각 분기 마다 그 분기의 최소한 가져야 하는 타일인 branch_max[k] 보다 작으면 탐색하지 않는 것이죠

두 번째 풀이 ( 배열, dfs 이용 )

이 부분도 오른쪽으로의 이동하는 경우로 설명드리겠습니다
간단하게 먼저 설명하자면 queue를 이용해서 0이 아닌 값을 담아 두고 하나씩 꺼내며 합치는 방법입니다.

1. 새로운 배열을 생성하고 queue에 0이 아닌값들을 담습니다. (이때 탐색은 행단위로 해내갑니다)
2. 오른쪽으로 이동이므로 오른쪽 끝(n-1)부터 탐색합니다.
3. queue에서 숫자를 하나 빼고 새로 만든 배열의 값이 0이라면(아무것도 쓰여있지 않음) 그 자리에 그 숫자를 씁니다.
   • 배열에 queue에서 뺀 값과 같은 값이 쓰여있다면 더해줘서 값을 2배로 하고 인덱스를 왼쪽(idx--)으로 이동합니다.
   • 0도 아니고 숫자도 같지 않다면 합쳐질 수 없으므로 그 자리에 숫자를 그 다음 인덱스(--idx)에 숫자를 써줍니다.

이 경우도 위와 아래로 이동하는 경우 모두 배열을 회전시켜 왼쪽으로 이동하는 함수와 오른쪽으로 이동하는 함수를
재사용 하였습니다.
arraylist에 값을 빼고 넣고 하는 것은 시간이 꽤 걸리기 때문에 이 경우가 훨씬 빠릅니다.

속도 비교

처음 맞은 경우는 1번경우로만 가지치기 한 경우고
두 번째 맞은 경우는 2번 경우도 가지치기 한 경우
세 번째는 arraylist를 이용하지 않고 배열을 이용해서 푼 경우에요. 속도차이가 압도적으로 나네요

12100 2048(easy) 자바 코드

코드가 길어서 불편 할 수 있기 때문에 깃 허브 주소를 따로 첨부하도록 하겠습니다.
1번 풀이(arrayList이용)
2번 풀이(배열 이용)

반례들

문제를 풀면서 다음 반례들을 참고하며 풀었습니다!!

• 1번

  3
  4 512 2
  512 2 64
  4 8 64
  correct answer : 1024

• 2번

  3
  64 2 128
  8 0 0
  64 2 8
  correct answer: 256

-3번

3
1024 32 512
0 256 128
128 0 0
correct answer: 2048

• 4번

  7
  2 2 2 2 2 2 2
  2 0 2 2 2 2 2
  2 0 2 2 2 2 2
  2 0 2 2 2 2 2
  2 2 2 0 2 2 2 
  2 2 2 2 2 2 0
  2 2 2 2 2 2 0
  correct answer: 32

• 5번

  10
  0 0 64 32 32 0 0 0 0 0
  0 32 32 64 0 0 0 0 0 0
  0 0 128 0 0 0 0 0 0 0 
  64 64 128 0 0 0 0 0 0 0
  0 0 64 32 32 0 0 0 0 0
  0 32 32 64 0 0 0 0 0 0
  0 0 128 0 0 0 0 0 0 0 
  64 64 128 0 0 0 0 0 0 0
  128 32 2 4 0 0 0 0 0 0
  0 0 128 0 0 0 0 0 0 0
  correct answer: 1024

• 6번

  10
  8 8 4 16 32 0 0 8 8 8
  8 8 4 0 0 8 0 0 0 0
  16 0 0 16 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 16
  0 0 0 0 0 0 0 0 0 2
  correct answer: 128

• 7번

  4
  2 4 8 16
  4 8 16 32
  8 16 32 64
  16 32 64 128
  correct answer: 128