평소에 해본 2048 게임. 상하좌우 방향으로 최대 5번 까지만 시행한다고 한다. 5번까지 상하좌우를 고르는 과정을 DFS로 구현하였다.
우선 main 함수에서 2048 초기값을 받고, 그 배열을 기준으로 dfs 수행
DFS
int depth : 상하좌우로 숫자를 몇 번 넘겼는지 확인하는 변수
depth == 5는 5번을 다 수행했다는 의미. 즉, dfs의 종료 조건이 된다.
종료 조건에서 v를 탐색하여 가장 큰 값을 변수 answer에 기억해둔다.
vector<vector<int>> v 와 solve(v, i)
solve(v, i)는 아래 solve 챕터에서 설명되어 있음
간단하게, i는 상하좌우 중 한 곳의 방향을 가리키고, v는 아직 i 방향으로 수행하기 이전의 배열을 넣는다. solve의 반환 값은 i 방향으로 이동을 마친 배열이다.
void dfs(vector<vector<int>> v, int depth){
if(depth == 5){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
answer = max(answer, v[i][j]);
return;
}
else {
for(int i = 0; i < 4; i++)
dfs(solve(v, i), depth + 1);
}
}
vector<vector<int>> solve(vector<vector<int>> v, int dir)
dir
따로 상하좌우를 나타내는 상수를 선언하여, dir에 들어온 값에 따라 상/하/좌/우를 구분하여 solve를 수행한다.
상하좌우 상수
const int RIGHT = 0;
const int LEFT = 1;
const int UP = 2;
const int DOWN = 3;
solve
dir는 상하좌우 중 한 곳의 방향을 가리키고, v는 아직 dir 방향으로 수행하기 이전의 배열을 넣는다. solve의 반환 값은 dir 방향으로 이동을 마친 배열이다.
dir == LEFT일 경우만 설명하겠다. 나머지의 경우는 다 비슷하고, 인덱스만 조금 바뀐다.
dir == LEFT일 경우
왼쪽으로 모든 숫자를 미는 것을 고려한다.
i
한 줄 씩 왼쪽으로 미니까, 가장 큰 for문인 i를 한 줄 씩 왼쪽으로 미는 용도 로 사용한다.
j
v[i][j]에 들어갈 수 있는 값을 찾는다. 즉, j의 자리에 들어올 숫자를 찾는다.
j는 자리를 위한 인덱스다.
k
v[i][j]에 들어갈 수 있는 값의 후보를 찾는다.
말이 조금 어려운데, v[i][j]의 값과 v[i][k]의 값에 따라서 v[i][j]에 들어갈 값이 달라지기 때문이다. 일단 코드의 주석을 보면서 이해해보자.
if(dir == LEFT){
// i : 모든 행을 검사해야 한다. (LEFT이기 때문에 행이지, UP이나 DOWN이라면 열을 검사해야 할 것이다.
for(int i = 1; i <= n; i++){
// j : v[i][j]에 들어갈 수 있는 값을 찾는다.
for(int j = 1; j <= n; j++){
// k : v[i][j]에 들어갈 수 있는 값의 후보를 찾는다.
for(int k = j + 1; k <= n; k++){
// 뒤의 값이 비어있는 경우에는 값의 후보가 될 수 없다.
// 왜냐하면, 값이 있어야 v[i][j]에 합쳐지거나, 그 뒤에 놓아지거나 할 것이다.
// 따라서 비어있는 경우에는 continue;
if(v[i][k] == 0) continue;
else {
// 값을 찾으려는 자리와 값의 후보의 값이 같다 == 하나의 숫자로 합쳐질 수 있다.
// 예를 들어, 2 0 0 2 와 같은 경우, j == 0, k == 3 이 된 경우라고 생각하자.
if(v[i][k] == v[i][j]){
v[i][j] *= 2;
// 값의 후보는 v[i][j]에 합쳐졌으므로, 0으로 초기화
v[i][k] = 0;
}
// 값을 찾으려는 자리와 값의 후보의 값이 다르다 == 하나의 숫자로 합쳐질 수 없다. 얹어져야 한다.
else {
// 근데 v[i][j]가 비었다? == 값의 후보는 v[i][j]로 들어와야 한다.
// 예를 들어, 0 0 0 2 와 같은 경우, j == 0, k == 3 이 된 경우라고 생각하자.
if(v[i][j] == 0){
v[i][j] = v[i][k];
v[i][k] = 0;
// j를 빼는 이유
// 0 2 0 2 와 같은 경우, j == 0, k == 1 이 된 경우라고 생각하자.
// 위의 코드 두 문장을 거친 이후, 2 0 0 2가 될 것이고, j-for 문이 끝나면서 j가 1이 되면, 앞의 2와 뒤의 2는 합쳐지지 못한다.
// j == 1, k == 3 이 되어서 그냥 2 2 0 0 이 될 것이다.
// 따라서, j를 한 번 빼줌으로써 이를 방지한다.
j--;
}
// 근데 v[i][j]가 비어있지 않다? == 값의 후보는 v[i][j + 1]로 들어와야 한다.
else{
// v[i][j]와 v[i][k]가 바로 붙어있지 않다면?
// 그냥 뒤에 두고, v[i][k]를 비워준다.
if(j + 1 != k){
v[i][j + 1] = v[i][k];
v[i][k] = 0;
}
// v[i][j]와 v[i][k]가 바로 붙어있다면?
// 예를 들어, 2 4 0 0 와 같은 경우, j == 0, k == 1 이 된 경우라고 생각하자.
// 위 if문 코드를 수행하면 2 0 0 0 이 되어버린다.
// 이를 방지해주고자 위와 같은 if 문을 작성했다.
}
}
// 값을 처리했다면, break
break;
}
}
}
}
}
// RIGHT, UP, DOWN 생략
return v;
dir == LEFT를 dir == RIGHT / UP / DOWN으로 전환할 때의 주의점
왼쪽으로 모는 것과 오른쪽으로 모는 것은 for 문을 돌릴 때 숫자의 증가/감소의 차이가 존재한다.
왼쪽으로 모는 것과 위쪽으로 모는 것은 for 문을 돌릴 때 행/열의 인덱스를 주의해야하는 차이가 존재한다.
