[DFS, BFS] 백준 12100 2048(Easy) C++

 

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

0 조심(해당 방향으로 0 없애고, 합친 후 다시 0 없앰)

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, ans;

void dfs(vector<vector<int>> board, int depth) {
    if (depth == 5) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) ans = max(ans, board[i][j]);
        }
        return;
    }

    vector<vector<int>> boardCopy(n, vector<int>(n, 0));

    // 왼쪽
    fill(boardCopy.begin(), boardCopy.end(), vector<int>(n, 0));
    for(int i=0; i<n; i++) {
        int idx = 0;
        for(int j=0; j<n; j++) { // 0 확인, 같/다, 2개씩 합쳐짐
            if (board[i][j] == 0) continue;
            else if (boardCopy[i][idx] == 0) boardCopy[i][idx] = board[i][j];
            else if (boardCopy[i][idx] == board[i][j]) boardCopy[i][idx++] = board[i][j] * 2;
            else boardCopy[i][++idx] = board[i][j];
        }
    }
    dfs(boardCopy, depth+1);

    // 오른쪽
    fill(boardCopy.begin(), boardCopy.end(), vector<int>(n, 0));
    for(int i=0; i<n; i++) {
        int idx = n-1;
        for(int j=n-1; j>=0; j--) {
            if (board[i][j] == 0) continue;
            else if (boardCopy[i][idx] == 0) boardCopy[i][idx] = board[i][j];
            else if (boardCopy[i][idx] == board[i][j]) boardCopy[i][idx--] = board[i][j] * 2;
            else boardCopy[i][--idx] = board[i][j];
        }
    }
    dfs(boardCopy, depth+1);

    // 위쪽
    fill(boardCopy.begin(), boardCopy.end(), vector<int>(n, 0));
    for(int i=0; i<n; i++) {
        int idx = 0;
        for(int j=0; j<n; j++) {
            if (board[j][i] == 0) continue;
            else if (boardCopy[idx][i] == 0) boardCopy[idx][i] = board[j][i];
            else if (boardCopy[idx][i] == board[j][i]) boardCopy[idx++][i] = board[j][i] * 2;
            else boardCopy[++idx][i] = board[j][i];
        }
    }
    dfs(boardCopy, depth+1);

    // 아래쪽
    fill(boardCopy.begin(), boardCopy.end(), vector<int>(n, 0));
    for(int i=0; i<n; i++) {
        int idx = n-1;
        for(int j=n-1; j>=0; j--) {
            if (board[j][i] == 0) continue;
            else if (boardCopy[idx][i] == 0) boardCopy[idx][i] = board[j][i];
            else if (boardCopy[idx][i] == board[j][i]) boardCopy[idx--][i] = board[j][i] * 2;
            else boardCopy[--idx][i] = board[j][i];
        }
    }
    dfs(boardCopy, depth+1);
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    vector<vector<int>> board(n, vector<int>(n, 0));
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++)  cin >> board[i][j];
    }

    dfs(board, 0);

    cout << ans;

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int ans = 0;
int N = 0;

struct info {
	vector<vector<int>> arr;
	int depth;
};

vector<vector<int>> mov(vector<vector<int>> board, int d) {
    vector<vector<int>> boardCopy(N, vector<int>(N, 0));
	if (d == 0) {
		for (int i = 0; i < N; i++) {
			int idx = 0;
			for (int j = 0; j < N; j++) {
                if (board[i][j] == 0) continue;
                else if (boardCopy[i][idx] == 0) boardCopy[i][idx] = board[i][j];
                else if (boardCopy[i][idx] == board[i][j]) boardCopy[i][idx++] = board[i][j] * 2;
                else boardCopy[i][++idx] = board[i][j];
			}
		}
	}
	else if (d == 1) {
		for (int i = 0; i < N; i++) {
			int idx = N - 1;
			for (int j = N - 1; j >= 0; j--) {
                if (board[i][j] == 0) continue;
                else if (boardCopy[i][idx] == 0) boardCopy[i][idx] = board[i][j];
                else if (boardCopy[i][idx] == board[i][j]) boardCopy[i][idx--] = board[i][j] * 2;
                else boardCopy[i][--idx] = board[i][j];
			}
		}
	}
	else if (d == 2) {
		for (int i = 0; i < N; i++) {
			int idx = 0;
			for (int j = 0; j < N; j++) {
                if (board[j][i] == 0) continue;
                else if (boardCopy[idx][i] == 0) boardCopy[idx][i] = board[j][i];
                else if (boardCopy[idx][i] == board[j][i]) boardCopy[idx++][i] = board[j][i] * 2;
                else boardCopy[++idx][i] = board[j][i];
			}
		}
	}
	else {
		for (int i = 0; i < N; i++) {
			int idx = N - 1;
			for (int j = N - 1; j >= 0; j--) {
                if (board[j][i] == 0) continue;
                else if (boardCopy[idx][i] == 0) boardCopy[idx][i] = board[j][i];
                else if (boardCopy[idx][i] == board[j][i]) boardCopy[idx--][i] = board[j][i] * 2;
                else boardCopy[--idx][i] = board[j][i];
			}
		}
	}

	return boardCopy;
}

void bfs(vector<vector<int>> arr, int depth) {
	queue<info> q;

	q.push({ arr, depth });
	while (!q.empty()) {
		info temp = q.front();
		q.pop();

		if (temp.depth == 5) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (ans < temp.arr[i][j]) ans = temp.arr[i][j];
				}
			}
			continue;
		}

		for (int i = 0; i < 4; i++) {
			q.push({ mov(temp.arr, i), temp.depth + 1 });
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> N;

	vector<vector<int>> arr(N, vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) cin >> arr[i][j];
	}

	bfs(arr, 0);

	cout << ans;
}