12100번 : 2048(easy) 비트마스크

교훈 :

 

for 문 안에서 벡터 erase 할시 주의 할점:

for(int i=0; i<v.size(); i++){
	v.erase(v.begin()+i); //지웠으면
    i--; // 인덱스도 한칸 머물러 줘야한다.
}

비트마스크로 모든 경우의 수 구하기 :

// 비트 마스크로 모든 경우의 수 구하는법

for(int i=0; i<(1<<n); i++){
	//i는 2^n승가지의 경우의 수가 나온다.
}

 

정수를 4진수로 만드는 법 :

vector<int> gen(int k){
	vector<int> a(n);
	for(int i=0; i<n; i++){ // 이때 n은 4^n 경우의 수이다.
    	a[i] = k&3; // 0011과 엔드연산 즉, k%4 와 같다.
        k>>=2; // 2번 오른쪽 쉬프트 즉, k/4와 같다.
    }
    return a;
}

 

문제 풀고 느낀점:

문제를 잘 이해하지 못햇다.........

---

#include<iostream>
#include<vector>

using namespace std;

const int LIMIT = 5;

vector<int> gen(int k) { // 정수를 4진수로
	vector<int> a(LIMIT);
	for (int i = 0; i < LIMIT; i++) {
		a[i] = k & 3;
		k >>= 2;
	}
	return a;
}
bool valid(vector<int> a) {
	for (int i = 0; i < LIMIT-1; i++) {
		if (a[i] == a[i + 1]) return false;
	}
	return true;
}

void up(vector<vector<int> > &map, vector<vector<bool> > &v) {
	int n = map.size();
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) continue;
			if (map[i][j] == map[i - 1][j] && v[i][j] == false&&v[i-1][j]==false) {
				map[i - 1][j] *= 2;
				map[i][j] = 0;
				v[i - 1][j] = true;
				v[i][j] = false;
			}
			if (map[i - 1][j] == 0) {
				map[i - 1][j] = map[i][j];
				map[i][j] = 0;
				v[i - 1][j] = v[i][j];
				v[i][j] = false;
			}
		}
	}
}

void down(vector<vector<int> > &map, vector<vector<bool> > &v) {
	int n = map.size();
	for (int i = 0; i <n-1; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) continue;
			if (map[i][j] == map[i + 1][j] && v[i][j] == false&&v[i+1][j]==false) {
				map[i + 1][j] *= 2;
				map[i][j] = 0;
				v[i + 1][j] = true;
				v[i][j] = false;
			}
			if (map[i + 1][j] == 0) {
				map[i + 1][j] = map[i][j];
				map[i][j] = 0;
				v[i + 1][j] = v[i][j];
				v[i][j] = false;
			}
		}
	}
}

void right(vector<vector<int> > &map, vector<vector<bool> > &v) {
	int n = map.size();
	for (int j = 0; j < n - 1; j++) {
		for (int i = 0; i < n; i++) {
			if (map[i][j] == 0) continue;
			if (map[i][j] == map[i][j+1] && v[i][j] == false&&v[i][j+1]==false) {
				map[i][j+1] *= 2;
				map[i][j] = 0;
				v[i][j+1] = true;
				v[i][j] = false;
			}
			if (map[i][j+1] == 0) {
				map[i][j+1] = map[i][j];
				map[i][j] = 0;
				v[i][j+1] = v[i][j];
				v[i][j] = false;
			}
		}
	}
}

void left(vector<vector<int> > &map, vector<vector<bool> > &v) {
	int n = map.size();
	for (int j = n-1; j >0; j--) {
		for (int i = 0; i < n; i++) {
			if (map[i][j] == 0) continue;
			if (map[i][j] == map[i][j-1] && v[i][j] == false&& v[i][j-1] == false) {
				map[i][j-1] *= 2;
				map[i][j] = 0;
				v[i][j-1] = true;
				v[i][j] = false;
			}
			if (map[i][j -1] == 0) {
				map[i][j -1] = map[i][j];
				map[i][j] = 0;
				v[i][j - 1] = v[i][j];
				v[i][j] = false;
			}
		}
	}
}
void simulate(int k, vector<vector<int> > &map, vector<vector<bool> > &v) {
	switch(k){
		case 0: up(map,v); break;
		case 1:	down(map,v); break;
		case 2:	right(map,v); break;
		case 3:	left(map,v); break;
	}
}

int check(vector<vector<int> > map, vector<int> a) {
	int a_size = a.size();
	vector<vector<bool> > v(map.size(), vector<bool>(map.size()));
	int max = -1;
	int n = map.size();
	for (int i = 0; i < a_size; i++) {
		simulate(a[i], map,v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (max < map[i][j]) {
					max = map[i][j];
				}
			}
		}
	}
	return max;
}

int main() {
	int n;
	cin >> n;
	vector<vector<int> > map(n, vector<int>(n));

	int ans = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (ans < map[i][j]) {
				ans = map[i][j];
			}
		}
	}
	for (int k = 0; k < (1 << LIMIT*2); k++) {
		vector<int> a = gen(k);
		if (!valid(a)) continue;
		int cur = check(map,a); // 시뮬레이션
		if (ans < cur) {
			ans = cur;
		}
	}
	cout << ans << '\n';
	return 0;
}

-> 틀림... 왜 틀림?

 

-> 만약에 

2

2

2

라는게 있으면 

 

위로 올렸을때,

4

2

가 되야 함  

 

근데 위의 코드는 

2

4

로 만들었음 

 

그리고 ,, 0 이 있을때 압축? 해줘야뎀

0     2      2                           4

2     0      2                           0

0     2      0                           0

2 -->0 -->0    --> 압축 하고 -->0 

 

이렇게 만들어야뎀,

#include<iostream>
#include<vector>

using namespace std;

const int LIMIT = 5;

vector<int> gen(int k) { // 정수를 4진수로
	vector<int> a(LIMIT);
	for (int i = 0; i < LIMIT; i++) {
		a[i] = k & 3;
		k >>= 2;
	}
	return a;
}
bool valid(vector<int> a) {
	for (int i = 0; i < LIMIT-1; i++) {
		if (a[i] == a[i + 1]) return false;
	}
	return true;
}

void make_map(vector<vector<int> >  &map) {
	int n = map.size();
	vector< vector<int> > vmap(n,vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			vmap[j][i] = map[i][j];
		}
	}
	map = vmap;
}
void make_v(vector<vector<bool> >  &v) {
	int n = v.size();
	vector< vector<bool> > temp(n, vector<bool>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			temp[j][i] = v[i][j];
		}
	}
	v=temp;
}

void up(vector<vector<int> > &map, vector<vector<bool> > &v) {
	// map 돌리기
	make_map(map);
	make_v(v);
	int n = map.size();
	for (int i = 0; i < n; i++) { // 압축 : 0지우기
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				map[i].erase(map[i].begin() + j);
				map[i].push_back(0);
				v[i].erase(v[i].begin() + j);
				v[i].push_back(false);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n-1; j++) {
			if (map[i][j] == map[i][j + 1] && v[i][j] == false) {
				map[i][j] *= 2;
				map[i].erase(map[i].begin() + j + 1);
				map[i].push_back(0);
				v[i].erase(v[i].begin() + j + 1);
				v[i].push_back(false);
			}
		}
	}
	make_map(map);
	make_v(v);
}

void down(vector<vector<int> > &map, vector<vector<bool> > &v) {
	// map 돌리기
	make_map(map);
	make_v(v);
	int n = map.size();
	for (int i = 0; i < n; i++) {
		reverse(map[i].begin(), map[i].end());
		reverse(v[i].begin(), v[i].end());
	}
	for (int i = 0; i < n; i++) { // 압축 : 0지우기
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				map[i].erase(map[i].begin() + j);
				map[i].push_back(0);
				v[i].erase(v[i].begin() + j);
				v[i].push_back(false);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			if (map[i][j] == map[i][j + 1] && v[i][j] == false) {
				map[i][j] *= 2;
				map[i].erase(map[i].begin() + j + 1);
				map[i].push_back(0);
				v[i].erase(v[i].begin() + j + 1);
				v[i].push_back(false);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		reverse(map[i].begin(), map[i].end());
		reverse(v[i].begin(), v[i].end());
	}
	make_map(map);
	make_v(v);
}

void right(vector<vector<int> > &map, vector<vector<bool> > &v) {
	int n = map.size();
	for (int i = 0; i < n; i++) {
		reverse(map[i].begin(), map[i].end());
		reverse(v[i].begin(), v[i].end());
	}
	for (int i = 0; i < n; i++) { // 압축 : 0지우기
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				map[i].erase(map[i].begin() + j);
				map[i].push_back(0);
				v[i].erase(v[i].begin() + j);
				v[i].push_back(false);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			if (map[i][j] == map[i][j + 1] && v[i][j] == false) {
				map[i][j] *= 2;
				map[i].erase(map[i].begin() + j + 1);
				map[i].push_back(0);
				v[i].erase(v[i].begin() + j + 1);
				v[i].push_back(false);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		reverse(map[i].begin(), map[i].end());
		reverse(v[i].begin(), v[i].end());
	}
}

void left(vector<vector<int> > &map, vector<vector<bool> > &v) {
	int n = map.size();
	for (int i = 0; i < n; i++) { // 압축 : 0지우기
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				map[i].erase(map[i].begin() + j);
				map[i].push_back(0);
				v[i].erase(v[i].begin() + j);
				v[i].push_back(false);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			if (map[i][j] == map[i][j + 1] && v[i][j] == false) {
				map[i][j] *= 2;
				map[i].erase(map[i].begin() + j + 1);
				map[i].push_back(0);
				v[i].erase(v[i].begin() + j + 1);
				v[i].push_back(false);
			}
		}
	}
}
void simulate(int k, vector<vector<int> > &map, vector<vector<bool> > &v) {
	switch(k){
		case 0: up(map,v); break;
		case 1:	down(map,v); break;
		case 2:	right(map,v); break;
		case 3:	left(map,v); break;
	}
}

int check(vector<vector<int> > map, vector<int> a) {
	int a_size = a.size();
	vector<vector<bool> > v(map.size(), vector<bool>(map.size()));
	int max = -1;
	int n = map.size();
	for (int i = 0; i < a_size; i++) {
		simulate(a[i], map,v);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (max < map[i][j]) {
					max = map[i][j];
				}
			}
		}
	}
	return max;
}

int main() {
	int n;
	cin >> n;
	vector<vector<int> > map(n, vector<int>(n));

	int ans = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (ans < map[i][j]) {
				ans = map[i][j];
			}
		}
	}
	for (int k = 0; k < (1 << LIMIT*2); k++) {
		vector<int> a = gen(k);
		if (!valid(a)) continue;
		int cur = check(map,a); // 시뮬레이션
		if (ans < cur) {
			ans = cur;
		}
	}
	cout << ans << '\n';
	return 0;
}

 벡터를 이용해서 erase 해서 지우고 뒷부분을 0으로 채워줬는데 또 틀렸음.

 

일단 문제 자체를 잘못이해했음 

같은 방향으로 연속해서 움직이면 아무 변화가 없을꺼 같아서 valid함수를 넣어줬었고

그리고 한번 이동하면 그 블록은 영원히 바뀌지 않을 꺼라 생각해서 v 라는 bool 배열을 만들어 줬었는데

 

잘 못 이해 한것이고  한번 이동할때 연속해서 합쳐지지 않는다는 뜻이었음...

그리고 두번째 고친 코드에서는 map 과 v 배열을 지우고 추가해주는 부분에 있어서 

for문에서의 변수인 j 가 벡터를 erase 를 시켜줄때 마다 j--를 해줘야 정확한 인덱스에 맞춰진다는 것을 깜빡있고 있었음.

 

따라서 코드는 이렇게 고쳤다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int LIMIT = 5;

vector<int> gen(int k) { // 정수를 4진수로
	vector<int> a(LIMIT);
	for (int i = 0; i < LIMIT; i++) {
		a[i] = k & 3;
		k >>= 2;
	}
	return a;
}

void make_map(vector<vector<int> >  &map) {
	int n = map.size();
	vector< vector<int> > vmap(n,vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			vmap[j][i] = map[i][j];
		}
	}
	map = vmap;
}

void game(vector< vector<int> > &map) {
	int n = map.size();
	for (int i = 0; i < n; i++) { // 압축 : 0지우기
		int cnt = 0;
		for (int j = 0; j < map[i].size(); j++) {
			if (map[i][j] == 0) {
				map[i].erase(map[i].begin() + j);
				j--;
				cnt++;
			}
		}
		for (int j = 0; j < cnt; j++) {
			map[i].push_back(0);
		}
	}

	for (int i = 0; i < n; i++) {
		int cnt = 0;
		for (int j = 0; j < map[i].size() - 1; j++) {
			if (map[i][j] == map[i][j + 1]) {
				map[i][j] *= 2;
				map[i].erase(map[i].begin() + j + 1);
				cnt++;
			}
		}
		for (int j = 0; j < cnt; j++) {
			map[i].push_back(0);
		}
	}
}

void up(vector<vector<int> > &map) {
	// map 돌리기
	make_map(map);
	game(map);
	make_map(map);

}

void down(vector<vector<int> > &map) {
	// map 돌리기
	make_map(map);
	
	int n = map.size();
	for (int i = 0; i < n; i++) {
		reverse(map[i].begin(), map[i].end());
	}
	game(map);
	for (int i = 0; i < n; i++) {
		reverse(map[i].begin(), map[i].end());
	}
	make_map(map);

}

void right(vector<vector<int> > &map) {

	int n = map.size();
	for (int i = 0; i < n; i++) {
		reverse(map[i].begin(), map[i].end());
	}
	game(map);
	for (int i = 0; i < n; i++) {
		reverse(map[i].begin(), map[i].end());
	}
}

void left(vector<vector<int> > &map) {
	game(map);
}
void simulate(int k, vector<vector<int> > &map) {
	switch(k){
		case 0: up(map); break;
		case 1:	down(map); break;
		case 2:	right(map); break;
		case 3:	left(map); break;
	}
}

int check(vector<vector<int> > map, vector<int> a) {
	int a_size = a.size();
	int max = -1;
	int n = map.size();
	for (int i = 0; i < a_size; i++) {
		simulate(a[i], map);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (max < map[i][j]) {
					max = map[i][j];
				}
			}
		}
	}
	return max;
}

int main() {
	int n;
	cin >> n;
	vector<vector<int> > map(n, vector<int>(n));

	int ans = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (ans < map[i][j]) {
				ans = map[i][j];
			}
		}
	}
	for (int k = 0; k < (1 << LIMIT*2); k++) {
		vector<int> a = gen(k);
		int cur = check(map,a); // 시뮬레이션
		if (ans < cur) {
			ans = cur;
		}
	}

	cout << ans << '\n';
	return 0;
}

 확실히 bfs 로 풀 때 보다 시간이 길진 하지만, 36ms 로 통과함. ㅋㄷㅋㄷ

 

 

 

이건 백준 코드 ,,,, 합쳐졌는지 안합쳐졌는지 t/f 로 구분하여 while 문을 통해서 한칸씩 계속 업데이트를 해줘서 느리다.

#include<iostream>
#include<cassert>
#include<vector>
#include<string>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
const int LIMIT = 5;
vector<int> gen(int k) {
	vector<int> a(LIMIT);
	for (int i = 0; i < LIMIT; i++) {
		a[i] = (k & 3);
		k >>= 2;
	}
	return a;
}
int check(vector<vector<int>> &a, vector<int> &dirs) {
	int n = a.size();
	vector<vector<pair<int, bool>>> d(n, vector<pair<int, bool>>(n));
	for (int i = 0; i < n; i++) { // map 넣어줌
		for (int j = 0; j < n; j++) {
			d[i][j].first = a[i][j];
		}
	}
	//0:down , 1:up, 2:left, 3:right
	for (int dir : dirs) { // 방향 순차적으로 for문
		bool ok = false;
		for (int i = 0; i < n; i++) { // bool false 로 초기화
			for (int j = 0; j < n; j++) {
				d[i][j].second = false;
			}
		}
		while (true) { // while 문을 돌면서 for문을 통해 계속 업데이트 해준다.
			ok = false;
			if (dir == 0) {
				for (int i = n - 2; i >= 0; i--) {
					for (int j = 0; j < n; j++) {
						if (d[i][j].first == 0) continue;
						if (d[i + 1][j].first == 0) { // 밑에가 0이면 밑으로 바로 내리기
							d[i + 1][j].first = d[i][j].first;
							d[i + 1][j].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i + 1][j].first == d[i][j].first) { // 밑에랑 같으면 
							if (d[i][j].second == false && d[i + 1][j].second == false) {
								d[i + 1][j].first *= 2;
								d[i + 1][j].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 1) {
				for (int i = 1; i < n; i++) {
					for (int j = 0; j < n; j++) {
						if (d[i][j].first == 0) continue;
						if (d[i - 1][j].first == 0) {
							d[i - 1][j].first = d[i][j].first;
							d[i - 1][j].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i - 1][j].first == d[i][j].first) {
							if (d[i][j].second == false && d[i - 1][j].second == false) {
								d[i - 1][j].first *= 2;
								d[i - 1][j].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 2) {
				for (int j = 1; j < n; j++) {
					for (int i = 0; i < n; i++) {
						if (d[i][j].first == 0) continue;
						if (d[i][j - 1].first == 0) {
							d[i][j - 1].first = d[i][j].first;
							d[i][j - 1].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i][j - 1].first == d[i][j].first) {
							if (d[i][j].second == false && d[i][j - 1].second == false) {
								d[i][j - 1].first *= 2;
								d[i][j - 1].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 3) {
				for (int j = n - 2; j >= 0; j--) {
					for (int i = 0; i < n; i++) {
						if (d[i][j].first == 0) continue;
						if (d[i][j + 1].first == 0) {
							d[i][j + 1].first = d[i][j].first;
							d[i][j + 1].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i][j + 1].first == d[i][j].first) {
							if (d[i][j].second == false && d[i][j + 1].second == false) {
								d[i][j + 1].first *= 2;
								d[i][j + 1].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			if (ok == false) break; // 아무 변화가 없으면 브레이크 ..
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) { // 가장 큰 값 고르기
		for (int j = 0; j < n; j++) {
			if (ans < d[i][j].first) {
				ans = d[i][j].first;
			}
		}
	}
	return ans;
}
int main() {
	int n;
	cin >> n;
	vector<vector<int>> a(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	int ans = 0;
	for (int k = 0; k < (1 << (LIMIT * 2)); k++) {
		vector<int> dir = gen(k);
		int cur = check(a, dir);
		if (ans < cur) ans = cur;
	}
	cout << ans << '\n';
	return 0;
}

60ms 나옴.