728x90
반응형
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ12100
//
// Created by Hwayeon on 2021/10/17.
//
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int N;
int board[21][21] = {0, };
int copy_board[21][21] = {0, };
vector<int> cmds;
vector<int> temp;
long long max_block = 0;
void play_game(){
memcpy(copy_board, board, sizeof(board));
for(int i=0; i<cmds.size(); i++){
int d = cmds[i];
switch (d) {
//좌
case 0:
for(int y=0; y<N; y++){
for(int x=N-1; x>=0; x--){
if(copy_board[y][x] == 0) continue;
temp.push_back(copy_board[y][x]);
copy_board[y][x] = 0;
}
int xx = 0;
while(!temp.empty()){
int num = temp.back();
temp.pop_back();
if(!temp.empty() && temp.back() == num){
num += temp.back();
temp.pop_back();
}
copy_board[y][xx] = num;
xx++;
}
}
break;
//상
case 1:
for(int x=0; x<N; x++){
for(int y=N-1; y>=0; y--){
if(copy_board[y][x] == 0) continue;
temp.push_back(copy_board[y][x]);
copy_board[y][x] = 0;
}
int yy=0;
while(!temp.empty()){
int num = temp.back();
temp.pop_back();
if(!temp.empty() && temp.back() == num){
num += temp.back();
temp.pop_back();
}
copy_board[yy][x] = num;
yy++;
}
}
break;
//우
case 2:
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
if(copy_board[y][x] == 0) continue;
temp.push_back(copy_board[y][x]);
copy_board[y][x] = 0;
}
int xx = N-1;
while(!temp.empty()){
int num = temp.back();
temp.pop_back();
if(!temp.empty() && temp.back() == num){
num += temp.back();
temp.pop_back();
}
copy_board[y][xx] = num;
xx--;
}
}
break;
//하
case 3:
for(int x=0; x<N; x++){
for(int y=0; y<N; y++){
if(copy_board[y][x] == 0) continue;
temp.push_back(copy_board[y][x]);
copy_board[y][x] = 0;
}
int yy=N-1;
while(!temp.empty()){
int num = temp.back();
temp.pop_back();
if(!temp.empty() && temp.back() == num){
num += temp.back();
temp.pop_back();
}
copy_board[yy][x] = num;
yy--;
}
}
break;
}
}
}
void get_max_block(){
long long max_b = 0;
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
if(copy_board[y][x] > max_b) max_b = copy_board[y][x];
}
}
if(max_b > max_block) max_block = max_b;
}
void get_cmds(int cnt){
if(cnt == 5){
play_game();
get_max_block();
return;
}
for(int d=0; d<4; d++){
cmds.push_back(d);
get_cmds(cnt+1);
cmds.pop_back();
}
}
int main(int argc, const char * argv[]) {
cin >> N;
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
cin >> board[y][x];
}
}
get_cmds(0);
cout << max_block << endl;
return 0;
}풀이 과정
풀이 시간 56분
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int N;
//원래 보드 상태를 저장하는 배열
int board[21][21] = {0, };
//시뮬레이션 할 보드
int copy_board[21][21] = {0, };
//5번의 이동 방향을 저장하는 벡터
vector<int> cmds;
//블록 값을 임시로 저장하는 벡터
vector<int> temp;
long long max_block = 0;
void play_game(){
//시뮬레이션 할 copy_board 초기화
memcpy(copy_board, board, sizeof(board));
//5번 이동 진행
for(int i=0; i<cmds.size(); i++){
int d = cmds[i];
switch (d) {
//좌
case 0:
for(int y=0; y<N; y++){
for(int x=N-1; x>=0; x--){
//블록이 없는 경우, 무시한다
if(copy_board[y][x] == 0) continue;
//블록이 있는 경우, temp에 담고 블록을 없앤다
temp.push_back(copy_board[y][x]);
copy_board[y][x] = 0;
}
int xx = 0;
while(!temp.empty()){
int num = temp.back();
temp.pop_back();
//그 다음 블록이 현재 블록과 값이 같은 경우, 합친다
if(!temp.empty() && temp.back() == num){
num += temp.back();
temp.pop_back();
}
copy_board[y][xx] = num;
xx++;
}
}
break;
//상
case 1:
for(int x=0; x<N; x++){
for(int y=N-1; y>=0; y--){
//블록이 없는 경우, 무시한다
if(copy_board[y][x] == 0) continue;
//블록이 있는 경우, temp에 담고 블록을 없앤다
temp.push_back(copy_board[y][x]);
copy_board[y][x] = 0;
}
int yy=0;
while(!temp.empty()){
int num = temp.back();
temp.pop_back();
//그 다음 블록이 현재 블록과 값이 같은 경우, 합친다
if(!temp.empty() && temp.back() == num){
num += temp.back();
temp.pop_back();
}
copy_board[yy][x] = num;
yy++;
}
}
break;
//우
case 2:
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
//블록이 없는 경우, 무시한다
if(copy_board[y][x] == 0) continue;
//블록이 있는 경우, temp에 담고 블록을 없앤다
temp.push_back(copy_board[y][x]);
copy_board[y][x] = 0;
}
int xx = N-1;
while(!temp.empty()){
int num = temp.back();
temp.pop_back();
//그 다음 블록이 현재 블록과 값이 같은 경우, 합친다
if(!temp.empty() && temp.back() == num){
num += temp.back();
temp.pop_back();
}
copy_board[y][xx] = num;
xx--;
}
}
break;
//하
case 3:
for(int x=0; x<N; x++){
for(int y=0; y<N; y++){
//블록이 없는 경우, 무시한다
if(copy_board[y][x] == 0) continue;
//블록이 있는 경우, temp에 담고 블록을 없앤다
temp.push_back(copy_board[y][x]);
copy_board[y][x] = 0;
}
int yy=N-1;
while(!temp.empty()){
int num = temp.back();
temp.pop_back();
//그 다음 블록이 현재 블록과 값이 같은 경우, 합친다
if(!temp.empty() && temp.back() == num){
num += temp.back();
temp.pop_back();
}
copy_board[yy][x] = num;
yy--;
}
}
break;
}
}
}
void get_max_block(){
long long max_b = 0;
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
if(copy_board[y][x] > max_b) max_b = copy_board[y][x];
}
}
//가장 큰 블록 갱신
if(max_b > max_block) max_block = max_b;
}
void get_cmds(int cnt){
//5번의 이동 방향을 정한 경우,
if(cnt == 5){
//게임 진행 -> O(N^2)
play_game();
//가장 큰 블록 구하기 -> O(N^2)
get_max_block();
return;
}
//이동 방향 정하기
for(int d=0; d<4; d++){
cmds.push_back(d);
get_cmds(cnt+1);
cmds.pop_back();
}
}
int main(int argc, const char * argv[]) {
cin >> N;
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
cin >> board[y][x];
}
}
//5번의 이동 방향에 대한 모든 경우의 수 구하기 -> 4^5
get_cmds(0);
cout << max_block << endl;
return 0;
}
//시간복잡도 = O(4^5*N^2), 공간복잡도 = O(N^2)
728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 19236 청소년 상어 C++ (0) | 2021.10.22 |
|---|---|
| 백준 16236 아기 상어 C++ (0) | 2021.10.20 |
| 백준 21611 마법사 상어와 블리자드 C++ (0) | 2021.10.15 |
| 백준 20056 마법사 상어와 파이어볼 C++ (0) | 2021.10.14 |
| 백준 21609 상어 중학교 C++ (0) | 2021.10.14 |