[BFS][삼성기출]백준12100번 2048(Easy)
업데이트:
백준12100 2048(Easy)
우리가 누구나 한 번쯤 해봤던 게임이기 때문에 문제는 금방 이해할 수 있었다. 하지만, 구현 부분에서 조금 까다로운 문제라고 생각한다. 다양한 방법이 있지만, 나는 bfs나 dfs 중 아무거나 사용해도 되는 문제라고 생각했고, 5번 이동할 때까지 모든 경우의 수를 탐색하기 위해 bfs를 사용했다. 중복순열을 통해 움직일 수 있는 경우의 수 (방향)의 가짓수를 모두 구하고 그 순서대로 이동하는 방법도 있는 것 같다.
BFS를 사용하기로 마음은 먹었지만 어떻게 접근해야 할 지 잘 감이 오지 않았다. 기존에 풀었던 삼성 기출 문제 중 문제와도 비슷할 것이라고 생각했는데, 구슬 탈출 문제에서는 두 개의 구술에 대해서만 bfs를 하면 됐지만 이번에는 블록의 개수가 정해져 있지 않아 전체 배열에 대해 bfs를 수행해야 한다고 생각했다. 따라서 다음과 같은 문제에 대해 고민했다.
- 어떻게 전체 배열에 대한 bfs를 수행할 것인가?
- 전체 블록을 이동하는 방법은 어떻게 구현할 것인가?
- 블록끼리 합쳐지는 조건은 어떻게 구현할 것인가?
또한, 위의 문제들의 구현에 앞서 구현의 편의를 위해 전체 배열은 block 구조체를 가지는 것으로 두었다.
struct block{
int y, x, val;
bool gathered;
};
좌표를 나타내는 y,x 변수와 블록의 값을 나타내는 val 변수, 한 번의 이동에서 블록이 이미 합쳐진 상태인지 아닌지를 나타내주는 bool 변수를 원소로 가진다.
1. 어떻게 전체 배열에 대한 bfs를 수행할 것인가?
머리속으로는 queue에 2차원 배열을 넣으면 되겠지 라고 생각했는데, 막상 구현을 하려고 하니 문법적으로 맞지 않는다는 에러창만 볼 수 있었다. 검색 끝에 다음과 같은 방법을 찾았다.
struct s {
int arr[10][10];
};
queue<struct s> q;
이런 식으로 배열을 구조체로 한 번 감싼 뒤 해당 구조체를 원소로 가지는 queue를 이용하여 bfs를 수행했다. BFS 방법을 이용하면 그 때 그 때 전체 배열의 상태를 기억(복사, 저장) 할 필요가 없기 때문에 그런 부분에서는 편리하다고 생각했다.
2. 전체 블록을 이동하는 방법은 어떻게 구현할 것인가?
단순히 배열을 이동하는 것 뿐만 아니라 배열을 이동하는 와중에 같은 수를 가지는 블럭을 만나면 합쳐주고, 심지어 한 번 합쳐진 블록은 합쳐지지 않게 해줘야 하기 때문에 한 번에 구현하면 너무 복잡해진다. 한참을 고민하다가 문제를 나눠서 생각하기로 했다.
우선, 주어진 블록을 전부 특정 방향으로 이동시키는 방법에 대해 생각해보았다. 전체 블록을 이동시키려면, 모든 블록들이 이동시키려는 방향 쪽으로 붙어야 한다. 이 문제를 조금 단순하게 생각하기 위해 모든 블록들이 자신이 가려는 방향으로 인접한 배열에 0이 나오지 않을 때까지 이동하는 것으로 생각하였다. 따라서 반복문을 통해 배열 내의 모든 블록에 대해 위와 같은 동작을 수행하도록 구현해주었다.
for(int i=1;i<N;i++){
for(int j=0;j<N;j++){
if(s.map[i][j].val !=0){
int tmp = 1;
while(i-tmp>=0 && s.map[i-tmp][j].val ==0){
tmp++;
}
tmp--;
if(tmp >0){
s.map[i-tmp][j].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
위의 코드는 모든 블록을 윗 방향으로 붙게 하는 코드이다.
배열 내의 모든 블록에 대해, (0번째 행은 제외했다. 위로 이동할 곳이 없기 때문이다.)
만약 자신이 0이 아니라면
- 배열의 범위를 벗어나지 않고
- 자신이 가려는 방향의 바로 앞 블록이 0일 때까지 (0이 아닌 것이 나오면 탈출)
tmp 변수를 증가하게 하였다. 제자리를 검사해야 할 필요는 없기 때문에 tmp 변수는 1에서 시작하도록 하고, 조건에 맞지 않아 탈출한 경우 1을 감소시킨 뒤 사용하였다.
만약 tmp 변수가 0보다 크다면 (한 칸 이상 이동했다면) 해당 위치와 현재 내 위치를 바꾸고 원래 있던 위치(시작 위치)를 0으로 바꿔주었다. (해당 위치와 내 위치 사이는 전부 0이기 때문에)
이제 블록을 모두 이동시키는 방법은 성공했으니 같은 블록끼리는 합쳐줘야 한다. 따라서, 해당 방향으로 (가로 혹은 세로) 자신과 같은 값을 가지는 블록이 있다면 두 블록을 합쳤다. 다만, 문제의 조건에 이동하려는 방향의 칸이 먼저 합쳐져야 한다는 조건이 포함되어 있기 때문에 이동하고자 하는 방향의 끝에서부터 검사하도록 했다.
//merge
for(int i=0;i<N;i++){
for(int j=0;j<N-1;j++){
if(s.map[j][i].val != 0 && !s.map[j][i].gathered && !s.map[j+1][i].gathered){
if(s.map[j][i].val == s.map[j+1][i].val){
s.map[j][i].val += s.map[j+1][i].val;
s.map[j+1][i].val = 0;
s.map[j][i].gathered = true;
}
}
}
}
위의 코드는 모든 블록을 위로 이동시킨 뒤 인접한 배열끼리 합쳐주는 역할을 한다.
배열을 위로 붙였기 때문에 열 단위로 검사하고, 위에 있는 블록부터 먼저 합쳐져야 하기 때문에 위에서부터 검사하도록 하였다. 가장 아래 행은 합쳐질 거면 자신의 위에 있는 블록에 의해 먼저 합쳐졌을 것이므로 검사하지 않도록 했다.
블록을 합치는 조건은 우선
- 자신의 값이 0이 아니어야 하고
- 내가 이번 이동에서 다른 블록과 합친 적이 없어야 하며
- 상대 블록과 나의 값이 같고
- 상대 블록도 이번 이동에서 다른 블록과 합쳐진 적이 없어야 한다.
블록을 합칠 때는 상대 블록의 값을 나에게 더하고 상대 블록을 0으로 만든뒤 나의 flag를 true로 변경하여 이번 이동에서 다른 블록과 합쳐졌음을 나타낸다.
이제 블록을 합치는 일까지는 마무리 했는데, 아직 문제가 남았다. 바로 합치는 과정에서 블록을 0으로 만들었으니 그 빈자리를 메꿔줘야 한다. 예를들어
2 2 2 2
2 2 2 2
2 0 2 2
2 0 2 2
와 같이 위로 이동을 수행한 배열에서 블록 합치기를 수행했다고 가정하면
4 4 4 4
0 0 0 0
4 0 4 4
0 0 0 0
이 된다. 중간에 빈칸이 생기게 된다. 따라서 블록 위로 이동을 한번 더 수행해준다. 이 경우 같은 값을 가진 블록들이 다시 만날 수 있지만 이미 한 번 합치기를 수행할 수 있는 블록들에 대해서는 모두 합치기를 수행했기 때문에 다시 수행하지 않는다.
위와 같은 과정을 거쳐 만든 “위로 이동하고 블록 합치기” 코드는 다음과 같다.
if(y_dir == 1){
// cout << "up depth: " << s.depth << "\n";
//pull up
for(int i=1;i<N;i++){
for(int j=0;j<N;j++){
if(s.map[i][j].val !=0){
int tmp = 1;
while(i-tmp>=0 && s.map[i-tmp][j].val ==0){
tmp++;
}
tmp--;
if(tmp >0){
s.map[i-tmp][j].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
//merge
for(int i=0;i<N;i++){
for(int j=0;j<N-1;j++){
if(s.map[j][i].val != 0 && !s.map[j][i].gathered && !s.map[j+1][i].gathered){
if(s.map[j][i].val == s.map[j+1][i].val){
s.map[j][i].val += s.map[j+1][i].val;
s.map[j+1][i].val = 0;
s.map[j][i].gathered = true;
}
}
}
}
//pull up
for(int i=1;i<N;i++){
for(int j=0;j<N;j++){
if(s.map[i][j].val !=0){
int tmp = 1;
while(i-tmp>=0 && s.map[i-tmp][j].val ==0){
tmp++;
}
tmp--;
if(tmp >0){
s.map[i-tmp][j].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
이를 바탕으로 아래, 양 옆으로 이동하는 코드를 추가하고, bfs를 수행하며 4방향을 모두 queue 에 넣어주면 된다. 조건을 만족하지 않거나 변경된 것이 없는 배열이 다시 queue에 들어갈 수는 있는데, 어차피 5번만 움직이면 되고 메모리 제한도 넉넉했기 때문에 굳이 예외 처리는 하지 않았다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N;
int arr[25][25];
struct block{
int y, x, val,tilted;
bool gathered;
};
struct state{
struct block map[25][25];
int depth;
};
//vector<struct block, vector<struct block> > map(25,vector<struct block>(25));
int y_iter[4] = {1,0,-1,0};
int x_iter[4] = {0,1,0,-1};
int answer = 0;
//vector<struct block> map[25];
struct state tilt(struct state s,int y_dir, int x_dir){
s.depth++;
if(y_dir != 0){
if(y_dir == 1){
// cout << "up depth: " << s.depth << "\n";
//pull up
for(int i=1;i<N;i++){
for(int j=0;j<N;j++){
if(s.map[i][j].val !=0){
int tmp = 1;
while(i-tmp>=0 && s.map[i-tmp][j].val ==0){
tmp++;
}
tmp--;
if(tmp >0){
s.map[i-tmp][j].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
//merge
for(int i=0;i<N;i++){
for(int j=0;j<N-1;j++){
if(s.map[j][i].val != 0 && !s.map[j][i].gathered && !s.map[j+1][i].gathered){
if(s.map[j][i].val == s.map[j+1][i].val){
s.map[j][i].val += s.map[j+1][i].val;
s.map[j+1][i].val = 0;
s.map[j][i].gathered = true;
}
}
}
}
//pull up
for(int i=1;i<N;i++){
for(int j=0;j<N;j++){
if(s.map[i][j].val !=0){
int tmp = 1;
while(i-tmp>=0 && s.map[i-tmp][j].val ==0){
tmp++;
}
tmp--;
if(tmp >0){
s.map[i-tmp][j].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
}
if(y_dir == -1){
//pull down
for(int i=N-1;i>=0;i--){
for(int j=0;j<N;j++){
if(s.map[i][j].val !=0){
int tmp = 1;
while(i+tmp<N && s.map[i+tmp][j].val ==0){
tmp++;
}
tmp--;
if(tmp > 0){
s.map[i+tmp][j].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
//merge
for(int i=0;i<N;i++){
for(int j=N-1;j>0;j--){
if(s.map[j][i].val != 0 && !s.map[j][i].gathered && !s.map[j-1][i].gathered){
if(s.map[j][i].val == s.map[j-1][i].val){
s.map[j][i].val += s.map[j-1][i].val;
s.map[j-1][i].val = 0;
s.map[j][i].gathered = true;
}
}
}
}
//pull down
for(int i=N-1;i>=0;i--){
for(int j=0;j<N;j++){
if(s.map[i][j].val !=0){
int tmp = 1;
while(i+tmp<N && s.map[i+tmp][j].val ==0){
tmp++;
}
tmp--;
if(tmp > 0){
s.map[i+tmp][j].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
}
}
else if(x_dir!=0){
if(x_dir == 1){
//pull right
for(int i = 0; i < N ; i ++){
for(int j=N-1;j>=0;j--){
if(s.map[i][j].val!=0){
int tmp = 1;
while(j+tmp < N && s.map[i][j+tmp].val == 0){
tmp++;
}
tmp--;
if(tmp > 0){
s.map[i][j+tmp].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
//merge
for(int i=0;i<N;i++){
for(int j=N-1;j>0;j--){
if(s.map[i][j].val != 0 && !s.map[i][j].gathered && !s.map[i][j-1].gathered){
if(s.map[i][j].val == s.map[i][j-1].val){
s.map[i][j].val += s.map[i][j-1].val;
s.map[i][j-1].val = 0;
s.map[i][j].gathered = true;
}
}
}
}
//pull right
for(int i = 0; i < N ; i ++){
for(int j=N-1;j>=0;j--){
if(s.map[i][j].val!=0){
int tmp = 1;
while(j+tmp < N && s.map[i][j+tmp].val == 0){
tmp++;
}
tmp--;
if(tmp > 0){
s.map[i][j+tmp].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
}
if(x_dir == -1){
//pull left
//cout << "left depth: " << s.depth << "\n";
for(int i = 0; i < N ; i ++){
for(int j=0;j<N;j++){
if(s.map[i][j].val!=0){
int tmp = 1;
while(j-tmp >=0 && s.map[i][j-tmp].val == 0){
tmp++;
}
tmp--;
if(tmp > 0){
s.map[i][j-tmp].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
//merge
for(int i=0;i<N;i++){
for(int j=0;j<N-1;j++){
if(s.map[i][j].val != 0 && !s.map[i][j].gathered && !s.map[i][j+1].gathered){
if(s.map[i][j].val == s.map[i][j+1].val){
s.map[i][j].val += s.map[i][j+1].val;
s.map[i][j+1].val = 0;
s.map[i][j].gathered = true;
}
}
}
}
//pull left
for(int i = 0; i < N ; i ++){
for(int j=0;j<N;j++){
if(s.map[i][j].val!=0){
int tmp = 1;
while(j-tmp >=0 && s.map[i][j-tmp].val == 0){
tmp++;
}
tmp--;
if(tmp > 0){
s.map[i][j-tmp].val = s.map[i][j].val;
s.map[i][j].val = 0;
}
}
}
}
}
}
//find max
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
//cout << s.map[i][j].val << " ";
s.map[i][j].gathered=false;
if(s.map[i][j].val > answer && s.depth<=5){
answer = s.map[i][j].val;
}
}
//cout << "\n";
}
//cout << "\n";
return s;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
struct state s;
s.depth = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
struct block tmp;
cin >> tmp.val;
tmp.y = i;
tmp.x = j;
tmp.tilted = 0;
tmp.gathered = false;
s.map[i][j] = tmp;
//map[i].push_back(tmp);
}
}
queue<state> q;
q.push(s);
while(!q.empty()){
struct state cur = q.front();
q.pop();
if(cur.depth==6){
cout << answer;
return 0;
}
for(int i=0;i<4;i++){
q.push(tilt(cur, y_iter[i], x_iter[i]));
}
}
}
전체 코드가 좀 길고 복잡한 구현을 가진 문제지만 개념 자체는 복잡하지 않았던 것 같다. 구현을 꾸준히 연습해 머리속에서 생각하는 알고리즘을 그대로 코드로 옮길 수 있는 능력을 갖춰야겠다.
댓글남기기