728x90
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<deque>
#include<math.h>
#include<cmath>
using namespace std;
int n;
//int arr[21][21];
int realMax = 0;
int findMax(vector<vector<int>>&arr) {
int maxnum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] > maxnum) {
maxnum = arr[i][j];
}
}
}
return maxnum;
}
void moveAllLeft(vector<vector<int>>&arr) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int idx = j - 1;
while (idx >= 0 && arr[i][idx] == 0) {
idx--;
}
idx++;
if (idx < j) {
arr[i][idx] = arr[i][j];
arr[i][j] = 0;
}
}
}
}
void moveAllRight(vector<vector<int>>&arr) {
for (int i = 0; i < n; i++) {
for (int j = n-1; j >= 0; j--) {
int idx = j+1;
while (idx <= n - 1 && arr[i][idx] == 0) {
idx++;
}
idx--;
if (idx > j) {
arr[i][idx] = arr[i][j];
arr[i][j] = 0;
}
}
}
}
void moveAllDown(vector<vector<int>>&arr) {
for (int j = 0; j < n; j++) {
for (int i = n-1; i >= 0; i--) {
int idx = i+1;
while (idx <= n - 1 && arr[idx][j] == 0) {
idx++;
}
idx--;
if (idx > i) {
arr[idx][j] = arr[i][j];
arr[i][j] = 0;
}
}
}
}
void moveAllUp(vector<vector<int>>&arr) {
for (int j = 0; j < n; j++) {
for (int i = 0; i <n; i++) {
int idx = i +-1;
while (idx >=0 && arr[idx][j] == 0) {
idx--;
}
idx++;
if (idx < i) {
arr[idx][j] = arr[i][j];
arr[i][j] = 0;
}
}
}
}
void simulateLeft(vector<vector<int>>&arr) {
moveAllLeft(arr); //왼쪽으로 모두 옮기기
for (int i = 0; i < n; i++) {
for (int j = 0; j < n-1; j++) {
if (arr[i][j] == arr[i][j + 1]) { //같은 거 찾으면 합쳐줌
arr[i][j] += arr[i][j + 1];
arr[i][j + 1] = 0;
//break;
}
}
}
moveAllLeft(arr);
}
void simulateRight(vector<vector<int>>&arr) {
moveAllRight(arr); //오른쪽으로 모두 옮기기
for (int i = 0; i < n; i++) {
for (int j = n-1; j >0; j--) {
if (arr[i][j] == arr[i][j - 1]) { //같은 거 찾으면 합쳐줌
arr[i][j] += arr[i][j - 1];
arr[i][j - 1] = 0;
// break;
}
}
}
moveAllRight(arr); //합쳐준 후에 중간에 빈칸이 없도록 옮겨줌
}
void simulateUp(vector<vector<int>>&arr) {
moveAllUp(arr); //위로 모두 옮기기
for (int j = 0; j < n; j++) {
for (int i = 0; i < n - 1; i++) {
if (arr[i][j] == arr[i+1][j]) { //같은 거 찾으면 합쳐줌
arr[i][j] += arr[i+1][j];
arr[i+1][j] = 0;
// break;
}
}
}
moveAllUp(arr);
}
void simulateDown(vector<vector<int>>&arr) {
moveAllDown(arr); //아래로 모두 옮기기
for (int j = 0; j < n; j++) {
for (int i = n-1; i > 0; i--) {
if (arr[i][j] == arr[i - 1][j]) { //같은 거 찾으면 합쳐줌
arr[i][j] += arr[i - 1][j];
arr[i - 1][j] = 0;
}
}
}
moveAllDown(arr);
}
//dfs를 통해 5번으로 갈수있는 모든 경우를 탐색한다.
void dfs(vector<vector<int>>&arr, int count) {
if (count == 5) {
int tmp = findMax(arr);
if (tmp > realMax) {
realMax = tmp;
}
return;
}
vector<vector<int>>tmpArr;
tmpArr = arr;
for (int i = 0; i < 4; i++) {
if (i == 0) {
simulateLeft(arr);
dfs(arr, count + 1);
arr = tmpArr;
}
else if (i == 1) {
simulateRight(arr);
dfs(arr, count + 1);
arr = tmpArr;
}
else if(i ==2){
simulateUp(arr);
dfs(arr, count + 1);
arr = tmpArr;
}
else if(i==3){
simulateDown(arr);
dfs(arr, count + 1);
arr = tmpArr;
}
}
return;
}
int main() {
cin >> n;
vector<vector<int>>arr(n,vector<int>(n,0));
vector<vector<int>>tmp;
queue<int>q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
dfs(arr, 0);
cout << realMax << endl;
}- DFS를 통해 모든 경우를 탐색하게된다.
- 한번 simulate 할때 움직이기 -> 합치기 -> 움직이기 를 했음
<JAVA>
package Samsung;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.*;
public class twozerofoureight {
static int n;
static int arr[][];
public static void move(int dir,int[][]arr) {
if(dir==0) { //위
boolean check[][] = new boolean[n][n]; //이미 합쳐진 블록을 기록, 이미 합쳐진것 -> true
for(int j=0; j<n; j++) { // 0 열~n열 탐색
for(int i=1; i<n; i++) { // 가장 윗부분에 한칸 떨어진 것부터 탐색
if(arr[i][j]!=0) { // 숫자가 있다면 움직이기, 없다면 움직이지 않는다
int t = i-1;
while(t >=0 && arr[t][j]==0){ // 위쪽방향에 숫자가 있는 곳을 찾는다
t --;
}
if(t<0) { //숫자가 하나도 없다면 가장 윗 부분에 숫자 저장
arr[t+1][j]=arr[i][j];
if((t+1)!=i)arr[i][j]=0; //찾은 곳이 자기자신이 아니라면 0으로 저장
}
else { //숫자가 있으면
if(arr[i][j]==arr[t][j]) { //만약 두 숫자가 같으면
if(!check[t][j]) { //한번 합친적이 없을때
arr[t][j]+=arr[i][j]; //합쳐준다
arr[i][j]=0; //기존 위치는 0으로 만들어준다
check[t][j]=true; //합쳤음을 기록
}
else {
arr[t+1][j]=arr[i][j]; //합친적이있으면 그 아랫부분에 저장
if((t+1)!=i)arr[i][j]=0; // 그 아랫부분이 원래위치와 같지 않을때만 0으로 변경
}
}
else { //만약 두 숫자가 다르면
arr[t+1][j]=arr[i][j]; //그 아랫부분저장
if((t+1)!=i)arr[i][j]=0; // 그 아랫부분이 원래위치와 같지 않을때만 0으로 변경
}
}
}
}
}
}
else if(dir ==1) { //아래
boolean check[][] = new boolean[n][n];
for(int j=0; j<n; j++) {
for(int i=n-2; i>=0; i--) {
if(arr[i][j]!=0) {
int t = i+1;
while(t<n&&arr[t][j]==0) {
t++;
}
if(t==n) {
arr[t-1][j]=arr[i][j];
if((t-1)!=i)arr[i][j]=0;
}
else {
if(arr[t][j]==arr[i][j]){
if(!check[t][j]) {
arr[t][j]+=arr[i][j];
arr[i][j]=0;
check[t][j]=true;
}
else {
arr[t-1][j]=arr[i][j];
if((t-1)!=i)arr[i][j]=0;
}
}
else {
arr[t-1][j]=arr[i][j];
if((t-1)!=i)arr[i][j]=0;
}
}
}
}
}
}
else if(dir ==2) { //왼
boolean check[][] = new boolean[n][n];
for(int i=0; i<n; i++) {
for(int j=1; j<n; j++) {
if(arr[i][j]!=0) {
int t = j-1;
while(t>=0 && arr[i][t]==0){
t--;
}
if(t<0) {
arr[i][t+1]=arr[i][j];
if((t+1)!=j) {arr[i][j]=0;}
}
else {
if(arr[i][t]==arr[i][j]) {
if(!check[i][t]) {
arr[i][t]+=arr[i][j];
arr[i][j]=0;
check[i][t]=true;
}
else {
arr[i][t+1]=arr[i][j];
if((t+1)!=j) {arr[i][j]=0;}
}
}
else {
arr[i][t+1]=arr[i][j];
if((t+1)!=j) {arr[i][j]=0;}
}
}
}
}
}
}
else if(dir==3) { //오
boolean check[][] = new boolean[n][n];
for(int i=0; i<n; i++) {
for(int j=n-2; j>=0; j--) {
if(arr[i][j]!=0) {
int t = j+1;
while(t<n && arr[i][t]==0){
t++;
}
if(t==n) {
arr[i][t-1]=arr[i][j];
if((t-1)!=j) {arr[i][j]=0;}
}
else {
if(arr[i][t]==arr[i][j]) {
if(!check[i][t]) {
arr[i][t]+=arr[i][j];
arr[i][j]=0;
check[i][t]=true;
}
else {
arr[i][t-1]=arr[i][j];
if((t-1)!=j) {arr[i][j]=0;}
}
}
else {
arr[i][t-1]=arr[i][j];
if((t-1)!=j) {arr[i][j]=0;}
}
}
}
}
}
}
}
static int realmax =0;
public static void dfs(int[][]arr, int cnt) {
if(cnt ==5) { //5번 움직였을때
int max=0;
for(int i=0;i<n;i++) {
for(int j=0; j<n; j++) {
if(arr[i][j]>max) {
max= arr[i][j]; //배열에서 가장큰 수 찾기
}
}
}
if(realmax<max) { //지금까지 가장 컸던 수와 현재 배열의 가장큰 수 비교하며 갱신
realmax=max;
}
return;
}
for(int i=0; i<4; i++) { // 상하좌우로 움직이기
int[][] tmp = new int[n][n]; // tmp 배열에 기존 상태를 저장
for(int p=0; p<n; p++) {
for(int q=0;q<n; q++) {
tmp[p][q]=arr[p][q];
}
}
move(i,arr); // 움직이기
dfs(arr, cnt+1); // 깊이 우선 탐색
for(int p=0; p<n; p++) { // 저장 했던 배열로 다시 상태 복구
for(int q=0;q<n; q++) {
arr[p][q]=tmp[p][q];
}
}
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(arr,0);
System.out.println(realmax);
}
}<2차>
package Samsung_2;
import java.io.*;
import java.util.*;
public class twoaerofoureight {
static int n;
static int[][]arr;
static int[]dx = {-1,1,0,0};
static int[]dy = {0,0,-1,1};
static int max =0;
public static boolean cango(int x, int y) {
return x>=0 && x<n && y>=0 && y<n;
}
public static void print() {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
static int kk =0;
public static void simulate(int[] order) {
for(int i=0; i<order.length; i++) {
boolean[][]check = new boolean[n][n];
int d =order[i];
// System.out.println(d);
//print();
if(d==0) { //위
for(int y=0; y<n; y++) {
for(int t=1; t<n; t++) {
//int tt = t;
int nx = t+dx[d];
int ny = y+dy[d];
while(cango(nx,ny)&&arr[nx][ny]==0) {
nx+=dx[d];
ny+=dy[d];
}
if(!cango(nx,ny)) {
nx-=dx[d];
ny-=dy[d];
if(!(nx==t && ny==y)) {
arr[nx][ny]=arr[t][y];
arr[t][y]=0;
}
continue;
}
if(arr[nx][ny]!=0) {
if(!(nx==t && ny ==y)) {
if(arr[nx][ny]==arr[t][y] && !check[nx][ny]) {
arr[nx][ny]*=2;
arr[t][y]=0;
check[nx][ny]=true;
}
else {
nx-=dx[d];
ny-=dy[d];
if(!(nx==t && ny ==y)) {
arr[nx][ny]=arr[t][y];
arr[t][y]=0;
}
}
}
}
else {
if(!(nx==t && ny ==y)) {
arr[nx][ny]=arr[t][y];
arr[t][y]=0;
}
}
}
}
}
else if(d==1) { //아래
for(int y=0; y<n; y++) {
for(int t=n-2; t>=0; t--) {
int nx = t+dx[d];
int ny = y+dy[d];
while(cango(nx,ny)&&arr[nx][ny]==0) {
nx+=dx[d];
ny+=dy[d];
}
if(!cango(nx,ny)) {
nx-=dx[d];
ny-=dy[d];
if(!(nx==t && ny==y)) {
arr[nx][ny]=arr[t][y];
arr[t][y]=0;
}
continue;
}
if(arr[nx][ny]!=0) {
if(!(nx==t && ny ==y)) {
if(arr[nx][ny]==arr[t][y] && !check[nx][ny]) {
arr[nx][ny]*=2;
arr[t][y]=0;
check[nx][ny]=true;
}
else {
nx-=dx[d];
ny-=dy[d];
if(!(nx==t && ny ==y)) {
arr[nx][ny]=arr[t][y];
arr[t][y]=0;
}
}
}
}
else {
if(!(nx==t && ny ==y)) {
arr[nx][ny]=arr[t][y];
arr[t][y]=0;
}
}
}
}
}
else if(d==2) { //왼
for(int x=0; x<n; x++) {
for(int p=1; p<n; p++) {
int nx = x+dx[d];
int ny = p+dy[d];
while(cango(nx,ny)&&arr[nx][ny]==0) {
nx+=dx[d];
ny+=dy[d];
}
if(!cango(nx,ny)) {
nx-=dx[d];
ny-=dy[d];
if(!(nx==x && ny==p)) {
arr[nx][ny]=arr[x][p];
arr[x][p]=0;
}
continue;
}
if(arr[nx][ny]!=0) {
if(!(nx==x && ny ==p)) {
if(arr[nx][ny]==arr[x][p] && !check[nx][ny]) {
arr[nx][ny]*=2;
arr[x][p]=0;
check[nx][ny]=true;
}
else {
nx-=dx[d];
ny-=dy[d];
if(!(nx==x && ny ==p)) {
arr[nx][ny]=arr[x][p];
arr[x][p]=0;
}
}
}
}
else {
if(!(nx==x && ny ==p)) {
arr[nx][ny]=arr[x][p];
arr[x][p]=0;
}
}
}
}
}
else if(d==3) { //오
for(int x=0; x<n; x++) {
for(int p=n-2; p>=0; p--) {
int nx = x+dx[d];
int ny = p+dy[d];
while(cango(nx,ny)&&arr[nx][ny]==0) {
nx+=dx[d];
ny+=dy[d];
}
if(!cango(nx,ny)) {
nx-=dx[d];
ny-=dy[d];
if(!(nx==x && ny==p)) {
arr[nx][ny]=arr[x][p];
arr[x][p]=0;
}
continue;
}
if(arr[nx][ny]!=0) {
if(!(nx==x && ny ==p)) {
if(arr[nx][ny]==arr[x][p] && !check[nx][ny]) {
arr[nx][ny]*=2;
arr[x][p]=0;
check[nx][ny]=true;
}
else {
nx-=dx[d];
ny-=dy[d];
if(!(nx==x && ny ==p)) {
arr[nx][ny]=arr[x][p];
arr[x][p]=0;
}
}
}
}
else {
if(!(nx==x && ny ==p)) {
arr[nx][ny]=arr[x][p];
arr[x][p]=0;
}
}
}
}
}
//System.out.println(d);
}
//print();
}
public static int getMax() {
int m=0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
m = Math.max(arr[i][j],m);
}
}
return m;
}
public static void permu(int[]order, int idx) {
if(idx==5) {
simulate(order);
int res = getMax();
max =Math.max(max, res);
return;
}
for(int i=0; i<4; i++) {
int[][] tmp = new int[n][n];
for(int p=0; p<n; p++) {
for(int q=0;q<n; q++) {
tmp[p][q]=arr[p][q];
}
}
order[idx]=i;
permu(order,idx+1);
for(int p=0; p<n; p++) {
for(int q=0;q<n; q++) {
arr[p][q]=tmp[p][q];
}
}
}
}
public static void main(String[]args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for(int i=0; i<n; i++) {
st= new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
permu(new int[5],0);
System.out.println(max);
}
}'백준 > 삼성기출' 카테고리의 다른 글
| 경사로- Java, 구현 (0) | 2021.04.02 |
|---|---|
| 스타트와 링크 - Java, 백트래킹 (0) | 2021.04.01 |
| 주사위 굴리기 (0) | 2021.03.27 |
| 시험감독 (0) | 2021.03.25 |
| 뱀 (0) | 2021.03.25 |