문제
문제 바로가기> BOJ 12100번: 2048 (Easy)
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
풀이
블록이 이동하는 순서를 미리 정해 놓은 뒤 시뮬레이션 해보는 문제다.
블록을 합칠 때, vector를 이용하면 좀 더 쉽게 문제를 해결할 수 있다.
C++
#include<iostream>
#include<vector>
#define MAX 21
#define CNT 5
using namespace std;
int N, ans=0;
int dir[CNT];
vector<int> tmp;
int map[MAX][MAX], init_map[MAX][MAX];
void input(){
cin >> N;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) cin >> init_map[i][j];
}
}
int get_max_val(){
int res = 0;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) res = max(res, map[i][j]);
} return res;
}
void move_up(){
for(int c=0; c<N; c++){
tmp.clear();
for(int r=0; r<N; r++){
if(map[r][c]!=0) tmp.push_back(map[r][c]);
map[r][c] = 0;
}
int r=0, idx=0;
while(idx < tmp.size()){
if(idx+1 < tmp.size() && tmp[idx] == tmp[idx+1]){
map[r++][c] = tmp[idx]*2;
idx+=2;
}
else map[r++][c] = tmp[idx++];
}
}
}
void move_down(){
for(int c=0; c<N; c++){
tmp.clear();
for(int r=N-1; r>=0; r--){
if(map[r][c]!=0) tmp.push_back(map[r][c]);
map[r][c] = 0;
}
int r=N-1, idx=0;
while(idx < tmp.size()){
if(idx+1 < tmp.size() && tmp[idx] == tmp[idx+1]){
map[r--][c] = tmp[idx]*2;
idx+=2;
}
else map[r--][c] = tmp[idx++];
}
}
}
void move_left(){
for(int r=0; r<N; r++){
tmp.clear();
for(int c=0; c<N; c++){
if(map[r][c]!=0) tmp.push_back(map[r][c]);
map[r][c] = 0;
}
int c=0, idx=0;
while(idx < tmp.size()){
if(idx+1 < tmp.size() && tmp[idx] == tmp[idx+1]){
map[r][c++] = tmp[idx]*2;
idx+=2;
}
else map[r][c++] = tmp[idx++];
}
}
}
void move_right(){
for(int r=0; r<N; r++){
tmp.clear();
for(int c=N-1; c>=0; c--){
if(map[r][c]!=0) tmp.push_back(map[r][c]);
map[r][c] = 0;
}
int c=N-1, idx=0;
while(idx < tmp.size()){
if(idx+1 < tmp.size() && tmp[idx] == tmp[idx+1]){
map[r][c--] = tmp[idx]*2;
idx+=2;
}
else map[r][c--] = tmp[idx++];
}
}
}
void solution(int cnt){
if(cnt == CNT){ // 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록 출력
// copy map
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) map[i][j] = init_map[i][j];
}
// move
for(int i=0; i<CNT; i++){
if(dir[i]==0) move_up();
else if(dir[i]==1) move_down();
else if(dir[i]==2) move_left();
else move_right();
}
// ans update
ans = max(ans, get_max_val());
return;
}
for(int i=0; i<4; i++){
dir[cnt] = i; // 이동 방향 설정
solution(cnt+1);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
input();
solution(0);
cout << ans;
}
Java
ArrayList를 사용했을 때, (아래 코드는 deque가 더 빨라서 바꾸긴 했는데)
tmp.get(idx) == tmp.get(idx+1) 로 검사하면 틀리고,
tmp.get(idx).equals(tmp.get(idx+1))로 검사해야 한다,,
Integer 객체이기 때문 ..... 킹받는다ㅎㅎ,,
근데 또 deque에서는 == 된다,, ^^,, 꺼내서 int 변수에 저장해서 그런가,, 하하
import java.io.*;
import java.util.*;
public class Main {
static int N, ans = 0;
static int[] dir = new int[5];
static int[][] init_map;
static Deque<Integer> tmp = new ArrayDeque<>();
public static void main(String[] args) throws Exception {
// System.setIn(new FileInputStream("res/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
// input
N = Integer.parseInt(br.readLine());
init_map = new int[N][N];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) init_map[i][j] = Integer.parseInt(st.nextToken());
}
// solution
solution(0);
// output
System.out.println(ans);
}
private static void solution(int cnt) {
if(cnt == 5){ // 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록 출력
// copy map
int[][] map = new int[N][N];
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) map[i][j] = init_map[i][j];
}
// move
for(int i=0; i<5; i++){
if(dir[i]==0) move_up(map);
else if(dir[i]==1) move_down(map);
else if(dir[i]==2) move_left(map);
else move_right(map);
}
// ans update
ans = Math.max(ans, get_max_val(map));
return;
}
for(int i=0; i<4; i++){
dir[cnt] = i; // 이동 방향 설정
solution(cnt+1);
}
}
private static void move_up(int[][] map) {
for(int c=0; c<N; c++){
tmp.clear();
for(int r=0; r<N; r++){
if(map[r][c]!=0) tmp.add(map[r][c]);
map[r][c] = 0;
}
int r=0;
while(!tmp.isEmpty()){
int num = tmp.poll();
if(!tmp.isEmpty() && num == tmp.peek()){
map[r++][c] = num*2;
tmp.poll();
}
else map[r++][c] = num;
}
}
}
private static void move_down(int[][] map) {
for(int c=0; c<N; c++){
tmp.clear();
for(int r=N-1; r>=0; r--){
if(map[r][c]!=0) tmp.add(map[r][c]);
map[r][c] = 0;
}
int r=N-1;
while(!tmp.isEmpty()){
int num = tmp.poll();
if(!tmp.isEmpty() && num == tmp.peek()){
map[r--][c] = num*2;
tmp.poll();
}
else map[r--][c] = num;
}
}
}
private static void move_left(int[][] map) {
for(int r=0; r<N; r++){
tmp.clear();
for(int c=0; c<N; c++){
if(map[r][c]!=0) tmp.add(map[r][c]);
map[r][c] = 0;
}
int c=0;
while(!tmp.isEmpty()){
int num = tmp.poll();
if(!tmp.isEmpty() && num == tmp.peek()){
map[r][c++] = num*2;
tmp.poll();
}
else map[r][c++] = num;
}
}
}
private static void move_right(int[][] map) {
for(int r=0; r<N; r++){
tmp.clear();
for(int c=N-1; c>=0; c--){
if(map[r][c]!=0) tmp.add(map[r][c]);
map[r][c] = 0;
}
int c=N-1;
while(!tmp.isEmpty()){
int num = tmp.poll();
if(!tmp.isEmpty() && num == tmp.peek()){
map[r][c--] = num*2;
tmp.poll();
}
else map[r][c--] = num;
}
}
}
private static int get_max_val(int[][] map) {
int res = 0;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) res = Math.max(res, map[i][j]);
} return res;
}
}'문제 풀이 > SW 역량 테스트' 카테고리의 다른 글
| BOJ 21611번: 마법사 상어와 블리자드 (0) | 2023.03.01 |
|---|---|
| BOJ 20056번: 마법사 상어와 파이어볼 (0) | 2023.02.20 |
| BOJ 17837번: 새로운 게임 2 (0) | 2023.02.08 |
| BOJ 15684번: 사다리 조작 (0) | 2023.02.06 |
| BOJ 17779번: 게리맨더링 2 (0) | 2023.02.04 |
