백준 12100 2048(Easy)

백준 12100←클릭

DFS를 이용하는 문제이다. 문제의 제한조건에서 DFS의 길이가 5층으로 제한되어 있기에 시간 복잡도는 크지 않다. DFS를 사용하는 것 보다 문제를 구현하는 것이 조금 귀찮은 문제다.

변수 설정

n: 현재 DFS의 층에 해당한다.
d: 움직임의 종류이다. 0부터 3의 값을 가지며 각각 ←,→,↓,↑에 해당하는 연산이다.
arr: 전체 2048배열을 저장한다. DFS이기 때문에 전역변수로 설정.
move: bool 변수로 이번 연산에서 배열에 움직임이 있었으면 true 아니면 false이다.
s: 스택의 개념으로 사용되는 변수로 어차피 하나의 수만 저장할 것이므로 int형으로 선언했다.
zero: 배 층마다 움직임 연산을 하는데 해당 층에 0이 있으면 zero가 true가 되고 이후 숫자가 나오면 move가 true가 된다.
now_v: 구현할 때 사용하는 벡터이다.

BFS 사용

• 매 DFS마다 현재 자신이 6층 이상이면 return한다.
  
  
• 자신의 층이 6층 이하이면 save배열에 현재 arr를 저장한다. (deep copy)
  
  
• 이번 DFS에 해당하는 연산을 수행한다.
  
  
• 이번 연산에서 움직임이 있다면 move가 true가 된다.
  
  
• move가 false이면 return한다
  
  
• move가 true이면 다음층의 DFS를 모두 실행한다. DFS(n+1, 0)~DFS(n+1, 3)
  
  
• 백트레킹을 위해 save배열에 저장되 있는 배열을 arr에 복사한다. (deep copy)

연산 구현

아래 규칙을 따르면 된다.

• 연산의 종류에 따라 for문을 돌며 now_v벡터에 층마다 수를 삽입한다. (0은 삽입하지 않는다.)
  
  
• 벡터의 크기만큼 for문을 돈다.
  
  
• 원소가 스택에 있는 수와 같은 경우 이전 원소now_v[j-1]를 삭제하고 현재 원소now_v[j]는 2배를 한 뒤, s를 삭제한다.
  
  
• 원소가 스택에 있는 수와 다른 경우 s에 있는 수를 삭제하고 now_v[j]를 삽입한다.
  
  
• 스택에 아무 것도 없으면 s에 now_v[j]를 넣는다.

위와 같은 예시가 있다고 하자. 위 배열에서 오른쪽으로 가는 연산이라면 위에서 부터 차례대로 가려는 방향(이번에는 오른쪽)부터 now_v에 삽입한다. 그러면 현재 now_v는

now_v	0	1	2	S
-	2	2	2

와 같이 만들어 진다.

위 규칙을 따르면 다음과 같이 진행된다. 벡터의 크기가 3이기 때문에 j는 0부터 2까지 간다.

j:0

now_v	0	1	2	S
-	2	2	2	2

s가 비어 있기 때문에 s에 now_v[0]가 들어가 s:2가 된다.

j:1

now_v	0	1	2	S
-	0	4	2	0

s의 값과 now_v[1]의 값이 같으므로 이전 값(now_v[0])은 0이 되고 now_v[1]은 2배가 되며 s값은 0이 된다.

j:2

now_v	0	1	2	S
-	0	4	2	2

s의 값이 비어있으므로 s의 값이 now_v[2]값으로 바뀐다.

이 연산 이후 now_v의 값들에서 0을 모두 제거한 뒤 arr배열에 순서대로 넣어주면 된다.

그러면 결과는

위와 같이 바뀔 것이다.

코드

github

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool print = false;
int MAX = 0, N;
int arr[21][21] = { 0, };
void dfs(int n, int d);
int main() {
	//freopen("input/12100_input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < 4; i++) {
		dfs(1, i);
	}
	cout << MAX << endl;
	return 0;
}
void dfs(int n, int d) {
	if (n > 5) return;
	bool move = false;
	int save[21][21];
	int front, s=0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			save[i][j] = arr[i][j];
		}
	}

	/*연산*/
	for (int i = 0; i < N; i++) {
		bool zero = false;
		/*d에 따라서 now_v생성*/
		vector<int> now_v;
		if (d == 0) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j]) { now_v.push_back(arr[i][j]); if (zero) move = true; }
				else if (!zero) zero = true;
			}
		}
		if (d == 1) {
			for (int j = N - 1; j >= 0; j--) {
				if (arr[i][j]) { now_v.push_back(arr[i][j]); if (zero) move = true; }
				else if (!zero) zero = true;
			}
		}
		if (d == 2) {
			for (int j = N - 1; j >= 0; j--) {
				if (arr[j][i]) { now_v.push_back(arr[j][i]); if (zero) move = true; }
				else if (!zero) zero = true;
			}
		}
		if (d == 3) {
			for (int j = 0; j < N; j++) {
				if (arr[j][i]) { 
					now_v.push_back(arr[j][i]); 
					if (zero) move = true;
				}
				else if (!zero) zero = true;
			}
		}
		s = 0;
		for (int j = 0; j < now_v.size(); j++) {
			if (!s) { //s가 0이면
				s = now_v[j];
			}
			else {
				if (now_v[j] == s) {
					now_v[j - 1] = 0;
					now_v[j] = 2 * s;
					s = 0;
					move = true;
				}
				else {
					s = now_v[j];
				}
			}
		}

		for (int j = 0; j < now_v.size(); j++) {
			if (!now_v[j]) now_v.erase(now_v.begin() + j);
		}
		if (now_v.size()) {
			for (int j = 0; j < now_v.size(); j++) {
				if (MAX < now_v[j]) {
					MAX = now_v[j];
				}
				if (d == 0) {
					arr[i][j] = now_v[j];
				}
				if (d == 1) {
					arr[i][N-j-1] = now_v[j];

				}
				if (d == 2) {
					arr[N-j-1][i] = now_v[j];
				}
				if (d == 3) {
					arr[j][i] = now_v[j];
				}
			}
			for (int j = now_v.size(); j < N; j++) {
				if (d == 0) {
					arr[i][j] = 0;
				}
				if (d == 1) {
					arr[i][N - j - 1] = 0;
				}
				if (d == 2) {
					arr[N - j - 1][i] = 0;
				}
				if (d == 3) {
					arr[j][i] = 0;
				}
			}
		}
	}
	/*연산 끝*/

	if (!move) {  
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = save[i][j];
			}
		}
		return; 
	}
	else {
		for (int i = 0; i < 4; i++) {
			dfs(n+1, i);
		}
		/*백트레킹*/
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = save[i][j];
			}
		}
	}
}

느낀점

비교적 빠르게 구현에 성공하였는데 자꾸 1초만에 틀렸습니다가 떴다. 질문 게시판에 있는 모든 TC를 통과했는데도 계속 틀렸대서 배열 크기도 바꿔보고 그랬는데 안되길래 칼바람 몇판하고 다시 코드를 보니 freopen으로 input을 불러오는 코드를 주석처리 안했었다...
추가적으로 2048(hard)문제도 풀어봐야 겠다. 같은 문제인데 10층까지 내려가야 하므로 시간 복잡도를 줄여야 한다.

정답~.~