백준 2048 (Easy) (Gold 2)

2048 게임을 어느 방향이든 5번 실행했을 경우 가장 큰 숫자를 출력하는 문제입니다.

 

문제를 읽고 이번 문제는 2048게임 구현 + 모든 경우의 수를 살펴 봐야겠다는 생각을 했습니다.

우선 구현부분에 대해 생각해봤습니다.

 

2048게임 동작 원리

한 가지 방향에 대해 밀기를 할 때 동작하는 원리에 대해 우선 파악했습니다.

밀었을 때 일어나는 현상은 간단하게 두 가지 였습니다.

1. 두 블럭이 같은 숫자라면 합쳐진다.
2. 두 블럭이 다른 숫자라면 나란히 놓여진다.

여기서, 몇 가지 조건이 추가되는데 이는 빈 공백이 있을 경우입니다.

이 게임은 모든 칸에 숫자가 적혀있는 것이 아니라 공백이 있을 수도 있기 때문에 공백이 있을 경우도 생각하며 구현을 해야합니다.

 

구현

숫자를 가져오고 합칠 수 있는 방법에 대해 많이 고민했었습니다. 저와 같은 경우 현재 숫자가 놓일 장소에 대한 인덱스와 숫자를 가져올 인덱스로 나누어 이를 해결했습니다.

숫자가 놓여지는 장소는 밀어지는 방향에서부터 차곡차곡 쌓이게 되기 때문에 숫자가 놓일 장소를 인덱스로 두고, 밀려지는 숫자들을 가져올 인덱스로 숫자들을 옮길 수 있도록 했습니다.

(아래 그림으로 이해를 돕도록 하겠습니다.)

예시 그림1

그림을 보면 숫자가 놓일 인덱스의 숫자와 숫자를 가져올 인덱스의 숫자를 비교해서 두 수를 합칠지, 두 수를 나란히 놓을 지 정하면 됩니다.

두 인덱스를 이동시키면서 해당 인덱스가 빈공간인지, 숫자인지 확인하고 두 인덱스의 숫자가 같은지 다른지도 비교하면서 동작되도록 했습니다.

 

 

위의 구현을 조건문으로 완성을 했습니다. 사용했던 조건은 다음과 같습니다.

(i행을 왼쪽으로 미는 경우를 예로 들겠습니다. j가 숫자를 놓을 인덱스이고 k가 숫자를 가져올 인덱스입니다.)

• board[i][j]==0 이고 temp[i][k]==0 이라면 아무일도 일어나지 않고 k만 1 증가시켜줍니다.
• board[i][j]==0 이고 temp[i][k]!=0 이라면 temp[i][j]=temp[i][k] 해주고 temp[i][k]=0 으로 바꿔줍니다. 이 때 k는 1 증가시키고 j는 증가시키지 않습니다. 그 이유는 현재 temp[i][k]의 숫자가 temp[i][j]로 이동 했으므로 temp[i][j]의 숫자는 아직 합쳐질 여지가 있기 때문입니다.

예시 그림2

위의 경우처럼 temp[i][j]가 빈칸인 상태에서 temp[i][k]에 있던 숫자가 들어오면 temp[i][j] 칸에서 새로운 숫자와 합쳐질 수 있기 때문에 j는 1 증가시키지 않습니다.

 

 

• temp[i][j]==temp[i][k] 일 경우 temp[i][j]에 있는 숫자를 2배시키고 temp[i][k]=0 대입, j와 k를 1 증가시켜줍니다. (두 숫자가 합쳐지는 경우입니다.)

그림 예시 3

 

• temp[i][j]가 0이 아니고 temp[i][j]!=temp[i][k] 일 경우는 두 가지로 나누어집니다.
  • temp[i][k]가 0일 경우 아무일도 일어나지 않고 k를 1 증가시켜 줍니다.
  • temp[i][k]가 0이 아닐 경우 temp[i][j]와 temp[i][k]는 서로 다른 숫자이므로 나란히 놓이게 됩니다. 이 때 조심해야될 것이 있습니다. (아래 설명)

그림 예시 4

위와 같이 각 인덱스가 가리키는 숫자가 달라 나란히 놓일 경우가 있습니다.

이 때, 평소처럼 temp[i][k]=0을 해주면 안됩니다. j+1==k 일 경우 temp[i][k]를 지우면 나란히 놓일 숫자 하나를 지울 수도 있기 때문에 이를 조심해 주어야합니다.

그러므로 temp[i][j+1]=temp[i][k]로 바꾸어주고, j+1!=k 일 경우에만 temp[i][k]를 0으로 바꿔주어야 합니다. 이 후, j와 k를 1씩 증가시켜줍니다.

 

현재까지 한 방향의 구현이 완성되었습니다. 다른 방향의 구현의 경우 인덱스를 살며시 뒤집거나, 시작 위치를 다르게 해준다면 쉽게 재구현이 됩니다. (코드 길이가 길어지긴 합니다..)

 

모든 방향의 구현을 완료하면 재귀문을 통해 5번 이동을 완료한 뒤 가장 높은 숫자를 답으로 출력하면 됩니다!

 

 

 

 

 

 

 

오늘은 조금 구현이 필요한 문제를 풀어보고 싶어 부르트포스 종류를 풀어보았습니다. 역시 구현 문제는 차분하게 모든 구현의 경우의 수를 작성하고 풀면 가능하다는 것을 믿는 것이 중요한 것 같습니다.

 

문제 링크 : https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)