(백준 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번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
문제 풀이
흔히 볼 수 있는 행렬 내에서 구슬이라 블럭을 이동시키는 시뮬레이션 문제이다. 하지만 이 문제가 고난이도인 이유는 그 이외에도 구현해야 할 점과 예외처리 해야할 부분이 꽤 있기 때문이다.
이 문제의 구현점은 크게 3가지이다. 첫째로 행렬 내에서 각 방향으로의 블럭의 이동, 그리고 블럭끼리의 충돌 판정을 구현해야한다. 두번째는 백트래킹이다. 최대 5번 이동시켜서 가장 큰 블록을 찾아야 하므로 5번동안 4방향의 백트래킹을 구현해야한다.
세번째는 예외 처리이다. 문제를 보면 한 번의 이동에서 이미 합쳐진 블록은 다시 합쳐질 수 없다고 되어있다. 필자는 이 부분을 못봐서 틀렸는데 예제도 하나 뿐인데 여기서 찾기도 힘들어서 문제를 제대로 읽지 않았다면 틀리기 쉬운 부분이라 생각한다.
이 세 부분만 제대로 구현해내면 그리 어려운 부분은 없는 문제였다. 자세한 코드는 다음과 같다.
코드
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n;
int ans;
void check(vector<vector<int>> table) {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(table[i][j]>ans) {
ans=table[i][j];
}
}
}
}//최대 크기인 블럭을 찾아내는 함수
void exe(int dir, int count, vector<vector<int>> table) {
if(count==5) return;
int visited[21][21]={0,};//한번 합쳐진 블럭은 충돌에서 제외하기 위해
//visited 배열에서 체크해준다.
if(dir==0) {//왼쪽으로 이동시키는 함수
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(table[i][j]!=0) {//블럭을 만나면 다시 왼쪽으로 이동하며
//다른 블럭 등이 있는지 확인한다
for(int k=j-1; k>=0; k--) {
if(table[i][k]!=0) {
if(table[i][k]==table[i][j] && !visited[i][k]) {
table[i][k]+=table[i][k];
table[i][j]=0; visited[i][k]=1;
}//값이 같고 합쳐진적 없다면 블록을 합체
else {
table[i][k+1]=table[i][j];
if(k+1!=j) table[i][j]=0;
}//블럭을 만났지만 합체하지 않으면 다음칸에 배치
break;
}
else if(k==0) {
table[i][k]=table[i][j];
table[i][j]=0;
}//왼쪽 끝까지 가도 블럭이 없다면 왼쪽 끝에 블럭 배치
}
}
}
}
}//나머지는 방향만 다를 뿐 기능은 왼쪽으로 이동하는 것과 같다
else if(dir==1) {//우측으로 이동
for(int i=0; i<n; i++) {
for(int j=n-1; j>=0; j--) {
if(table[i][j]!=0) {
for(int k=j+1; k<n; k++) {
if(table[i][k]!=0) {
if(table[i][k]==table[i][j] && !visited[i][k]) {
table[i][k]+=table[i][k];
table[i][j]=0; visited[i][k]=1;
}
else {
table[i][k-1]=table[i][j];
if(k-1!=j) table[i][j]=0;
}
break;
}
else if(k==n-1) {
table[i][k]=table[i][j];
table[i][j]=0;
}
}
}
}
}
}
else if(dir==2) {//위로 이동
for(int j=0; j<n; j++) {
for(int i=0; i<n; i++) {
if(table[i][j]!=0) {
for(int k=i-1; k>=0; k--) {
if(table[k][j]!=0) {
if(table[k][j]==table[i][j] && !visited[k][j]) {
table[k][j]+=table[k][j];
table[i][j]=0; visited[k][j]=1;
}
else {
table[k+1][j]=table[i][j];
if(k+1!=i) table[i][j]=0;
}
break;
}
else if(k==0) {
table[k][j]=table[i][j];
table[i][j]=0;
}
}
}
}
}
}
else if(dir==3) {//아래로 이동
for(int j=0; j<n; j++) {
for(int i=n-1; i>=0; i--) {
if(table[i][j]!=0) {
for(int k=i+1; k<n; k++) {
if(table[k][j]!=0) {
if(table[k][j]==table[i][j] && !visited[k][j]) {
table[k][j]+=table[k][j];
table[i][j]=0; visited[k][j]=1;
}
else {
table[k-1][j]=table[i][j];
if(k-1!=i) table[i][j]=0;
}
break;
}
else if(k==n-1) {
table[k][j]=table[i][j];
table[i][j]=0;
}
}
}
}
}
}
check(table);//최대 값인 블럭이 있는지 확인
for(int i=0; i<4; i++) {
exe(i,count+1,table);
}//다시 4방향으로 재귀를 활용한 백트래킹
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
vector<vector<int>> table;
for(int i=0; i<n; i++) {
vector<int> v;
for(int j=0; j<n; j++) {
int a;
cin >> a;
v.push_back(a);
}
table.push_back(v);
}//백트래킹 할때는 배열 하나를 쓰는것보다 각자 하나씩 갖는게 편리하므로
//그리고 2차원 배열을 매개변수로 전달하기 힘드므로 주소값 전달 대신
//복사하여 함수에 전달하는 벡터를 배열 대신 사용
for(int i=0; i<4; i++) {
exe(i,0,table);
}
cout << ans;
}