문제 정보
백준 ( BOJ ) 12100 2048(easy)
문제 풀이 : stack,queue 를 이용한 bfs
문제 출처 : https://www.acmicpc.net/problem/12100
문제 풀이
우선 이 문제는 BFS로 모든 방향을 탐색해서 최고의 값을 찾아야 하는 문제입니다.
저는 그래서 moveL, moveR, moveD, moveU 이렇게 4가지로 나누어
void move(vector<vector<int>> square, int n) {
if (n != 5) {
move(moveL(square), n + 1);
move(moveR(square), n + 1);
move(moveD(square), n + 1);
move(moveU(square), n + 1);
}
}
이런식으로 BFS를 만들어 돌렸습니다.
BFS 사용이야 재귀로 하면 되고,
이제 어떻게 한쪽 방향으로 몰아야 할 지 생각을 해 봅시다.
우선 블럭을 한쪽 방향으로 몰아야 한다는 생각에 3중 포문을 사용하기 쉬운데
(사실 저도 처음에 그렇게 짰습니다.)
stack과 queue 를 이용하면 간단하게 짤 수가 있습니다.
우선 한 열이든 행이든 돌면서, 앞쪽으로 땡기려면 queue를, 뒤쪽으로 땡기려면 stack에 모두 넣어 줍니다.
쉬운 예시를 위해 행만 가지고 한번 생각을 해 보곘습니다.
2 2 4 2 4 4
queue : 2 2 4 2 4 4
이제 넣었는데 이를 어떻게 합쳐야 할까요?
먼저 맨 앞에꺼를 빼 냅니다.
temp : 2 / queue : 2 4 2 4 4
그리고, queue가 엠티인지 확인후, 엠티가 아니라면 프론트를 확인합니다.
다시 큐의 프론트와, temp 를 비교하여 같다면
큐를 팝 하고, temp *= 2 해 준 후
넣습니다.
4 / temp = 4 / queue : 2 4 4
4 4 / temp = 2 / queue : 4 4
4 4 2 / temp = 4 / queue : 4
4 4 2 / temp = 8 / queue : empty
4 4 2 4
만약 반대방향으로 땡겨야 하는경우, stack을 이용하면 됩니다.
( 똑같이 queue를 사용해 역방향으로 담아도 상관 없습니다. )
그렇다면 최대값은 어디서 구하는게 좋을까요?
최대값은 2군대에서 구할 수 있습니다.
각각 5번 움직인 최종에서 배열을 하나하나 검사하는 방법과,
temp 의 값에 2배를 해줄 때 최대값을 저장하는 방법이 있습니다.
편하신대로 하시면 되실 거 같습니다.
문제 코드
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
int squareSize = 0;
int best = 0;
vector<vector<int>> moveL(vector<vector<int>> square) {
queue<int> q;
for (int i = 0; i < squareSize; i++) {
for (int j = 0; j < squareSize; j++) {
if (square[i][j] != 0) {
q.push(square[i][j]);
square[i][j] = 0;
}
}
for (int j = 0; !q.empty(); j++) {
int temp;
temp = q.front();
q.pop();
if (!q.empty() && temp == q.front()) {
q.pop();
temp *= 2;
if (best < temp)
best = temp;
}
square[i][j] = temp;
}
}
return square;
}
vector<vector<int>> moveR(vector<vector<int>> square) {
stack<int> q;
for (int i = 0; i < squareSize; i++) {
for (int j = 0; j < squareSize; j++) {
if (square[i][j] != 0) {
q.push(square[i][j]);
square[i][j] = 0;
}
}
for (int j = squareSize-1; !q.empty(); j--) {
int temp;
temp = q.top();
q.pop();
if (!q.empty() && temp == q.top()) {
q.pop();
temp *= 2;
if (best < temp)
best = temp;
}
square[i][j] = temp;
}
}
return square;
}
vector<vector<int>> moveU(vector<vector<int>> square) {
queue<int> q;
for (int j = 0; j < squareSize; j++) {
for (int i = 0; i < squareSize; i++) {
if (square[i][j] != 0) {
q.push(square[i][j]);
square[i][j] = 0;
}
}
for (int i = 0; !q.empty(); i++) {
int temp;
temp = q.front();
q.pop();
if (!q.empty() && temp == q.front()) {
q.pop();
temp *= 2;
if (best < temp)
best = temp;
}
square[i][j] = temp;
}
}
return square;
}
vector<vector<int>> moveD(vector<vector<int>> square) {
stack<int> q;
for (int j = 0; j < squareSize; j++) {
for (int i = 0; i < squareSize; i++) {
if (square[i][j] != 0) {
q.push(square[i][j]);
square[i][j] = 0;
}
}
for (int i = squareSize - 1; !q.empty(); i--) {
int temp;
temp = q.top();
q.pop();
if (!q.empty() && temp == q.top()) {
q.pop();
temp *= 2;
if (best < temp)
best = temp;
}
square[i][j] = temp;
}
}
return square;
}
void move(vector<vector<int>> square, int n) {
if (n != 5) {
move(moveL(square), n + 1);
move(moveR(square), n + 1);
move(moveD(square), n + 1);
move(moveU(square), n + 1);
}
}
int main() {
int temp;
cin >> squareSize;
vector<vector<int>> square(squareSize, vector<int>(squareSize,0));
for (int i = 0; i < squareSize; i++) {
for (int j = 0; j < squareSize; j++) {
cin >> temp;
if (best < temp)
best = temp;
square[i][j] = temp;
}
}
move(square, 0);
cout << best;
cin >> temp;
}