[백준 12100] 2048(Easy) (자바)

백준 12100번 2048(Easy) (자바)

 

 

 

출처

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

 

 

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

 

 

 

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

 

 

입출력 예

입출력 예 1

 

 

 

걸린 시간

 

 

 

접근 방법

골드2 수준의 구현 문제다. 삼성 기출이기 때문에 유명한 문제다.

 

풀기 전에 게임을 꼭 해보시는 것을 추천드립니다ㅎㅎ(문제 이해가 쏙쏙 되거든요~)

 

총 5번 이동이 가능하기 때문에 방향 조합을 어떻게 만들지 고민을 많이 했는데 답은 dfs였다.

0~3방향을 크기가 5인 dir배열에 모든 경우의 수를 담음으로써 모든 경우를 탐색할 수 있었다.

 

기존 배열을 그대로 사용할 수 없으니 계산을 위한 배열을 만들어 기존 배열을 복사합니다.

 

이후 조합한 방향에 따라 배열 안의 값들을 이동시킵니다.

상, 하의 경우 열의 변화 없이 행의 변화만 있기 때문에 move메서드에 i,j 순서로 매개변수를 보내도 되지만,

좌, 우의 경우 행의 변화없이 열의 변화만 있기 때문에 열을 기준으로 j, i 순서로 매개변수를 보내야 한다.

 

해당 방향으로 이동 시 이동하는 방향에서 제일 가까운 수들이 먼저 이동한다.

이때 자신과 앞에 있는 수가 같으면 합치고, visit처리를 해주어 이미 합쳐진 블록이 또 합쳐질 수 없도록 한다.

자신과 다른 수가 있다면 합칠 수 없고, 배열 범위를 넘거나 이미 합쳐진 곳이면 메서드를 종료시킨다.

위 경우에 모두 해당하지 않는다면 값을 이동시키고, 이동 전 배열 값을 0으로 만든다.

 

이후에 배열에서 가장 큰 값을 뽑는다.

 

 

 

내 코드

 

 

 

고려할 점

1. dfs 사용

2. 4방향에 따라 이동 방향 생각

3. 합쳐진 곳 또 방문 불가능