❓ 문제 - 백준 2048(Easy) 12100번 - JAVA 풀이법
출처
(https://www.acmicpc.net/problem/12100)
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
*** 해결법만 빠르게 보실 분은들은 뒤(풀이법2)를 봐주세요 ^_^..***
1. 더 나은 코드, 효율적인 코드를 만들기 위해 노력 했습니다...
2.
1) 일단 처음 중복 조합 -> 해당 경우마다 다 움직이게 구현 후 최대값 갱신 ->출력
- 움직이게 하는 부분이 어려웠는데... 많은 노력 끝에 해결 했다.. 하지만 너무 코드가 길고..
- 시간, 공간적인 효율에 있어서도 큰 메리트가 없어서 다른 해결법이 있지 않나..? 고민했습니다..
- 혼자 여러 가지 경우를 고민해보다가 다른 사람들의 코드를 참고 했고 해결했습니다
2)
- 이동의 경우를 BFS로 해결하여 각 경우마다 움직이게 구현방법 찾았습니다..
- 실제로 JAVA에 맞게 코딩하면서 코드들도 더 짧아지고 효율성도 올라갈 수 있었다.
3) 결과
- 더 효율적인 알고리즘 생각해내는 천재만재들.... 부럽다...(시기,,,질투,,,)
- 나도 공부하다보면 더 좋은 코딩하겠지!
****
*** 꿀팁
테케는 맞는데 돌리면 틀렸습니다 뜨시는 분들... 내 거 블록이 해당 방향으로 싹 잘 밀렸나 print나 디버거로 확인해보세요 꼭....! 어떤 경우에는 잘 밀리고 앞에 있는 것들이 합쳐져서 더 밀림이 필요할 수도 있어요...!
📝 문제해결법 1
1. 이 문제는 DFS(중복조합) + 구현으로 풀이했다.
- permutation()이라는 함수를 통해 최대 5번 이동할 수 있으므로 5번의 이동 중복 조합을 구한다...
- 0(위로), 1(아래로), 2(왼쪽), 3(오른쪽)의 경우에 맞춰 이동할 수 있는 함수를 호출하여 map을 이동처리한다.
- 각 경우마다 map의 형태가 달라지므로 꼭...! 한 경우에서 map_copy로 map의 내용을 카피한 후, map_copy로 이동처리 해야한다!
2. 방향에 맞춰 이동 처리 구현
- up ( 아래로 이동하면서 블록 위로 이동하기 처리)
- 해당 블록들을 위로 이동시켜야 하므로 열단위로 움직이면서 해당 행에서 밑으로 내리면서 위로 올릴 수 있도록 구현하였다.
- 만약 밑으로 내려가다가 숫자가 있는데 자기 자신과 같고 합쳐진 적이 없는 블록이라면 자기 자신에 그 블록이 합쳐지고 해당 부분은 0으로 처리한 후, 나의 블록에 방문처리(합쳐짐 체크) 해준다.
- 만약 현재 살피는 기준인 행이 비어있는데 밑으로 내려가다가 숫자가 있으면 현재 내가 있는 행에 해당 값을 넣어주고 밑에 있는 부분에 0으로 처리하면서 블록을 위로 올려준다.
- 블록의 이동이 존재하면 카운트 시켜주는데 계속 돌면서 만약 블록의 이동처리가 끝나면(카운트=0)이면 해당 열의 모든 행 블록들은 이동처리가 끝난 것이다.
- 이런 카운트를 하는 이유가 한번 모든 행에서 위로 블록이 만약 합쳐진 것이 있거나 블록의 이동이 있으면 중간에 상태가 변경되므로 다시 돌면서 이동처리 해줘야함..
- down ( 위로 이동하면서 블록 아래로 내리기 처리)
- 해당 블록들을 아래로 이동시켜야 하므로 열단위로 움직이면서 맨 밑 행부터 위로 탐색하면서 아래로 내릴 수 있도록 구현하였다.
- 만약 위로 올라가다가 숫자가 있는데 자기 자신과 같고 합쳐진 적이 없는 블록이라면 자기 자신에 그 블록이 합쳐지고 해당 부분은 0으로 처리한 후, 나의 블록에 방문처리(합쳐짐 체크) 해준다.
- 만약 행을 살피는 기준인 현재 행이 비어있는데 위로 탐색하다가 숫자가 있으면 현재 내가 있는 행에 해당 값을 넣어주고 위에 있는 행 부분에 0으로 처리하면서 블록을 아래로 올려준다.
- 블록의 이동이 존재하면 카운트 시켜주는데 계속 돌면서 만약 블록의 이동처리가 끝나면(카운트=0)이면 해당 열의 모든 행 블록들은 이동처리가 끝난 것이다.
- 이런 카운트를 하는 이유가 한번 모든 행에서 아래로 블록이 만약 합쳐진 것이 있거나 블록의 이동이 있으면 중간에 상태가 변경되므로 다시 돌면서 이동처리 해줘야함..
- left (오른쪽으로 이동하면서 블록 왼쪽으로 당김 처리)
- 해당 블록들을 왼쪽으로 이동시켜야 하므로 열단위로 움직이면서 맨 왼쪽 열부터 오른쪽로 탐색하면서 왼쪽으로 이동시킬 수 있도록 구현하였다.
- 만약 오른쪽으로 이동하다가 숫자가 있는데 자기 자신과 같고 합쳐진 적이 없는 블록이라면 자기 자신에 그 블록이 합쳐지고 해당 부분은 0으로 처리한 후, 나의 블록에 방문처리(합쳐짐 체크) 해준다.
- 만약 열을 살피는 기준인 현재 열이 비어있는데 오른쪽으로 탐색하다가 숫자가 있으면 현재 내가 있는 행에 해당 값을 넣어주고 기존 열 부분에 0으로 처리하면서 블록을 왼쪽으로 이동시켜준다.
- 블록의 이동이 존재하면 카운트 시켜주는데 계속 돌면서 만약 블록의 이동처리가 끝나면(카운트=0)이면 해당 행의 모든 열 블록들은 이동처리가 끝난 것이다.
- 이런 카운트를 하는 이유가 한번 모든 열에서 왼쪽으로 블록이 만약 합쳐진 것이 있거나 블록의 이동이 있으면 중간에 상태가 변경되므로 다시 돌면서 이동처리 해줘야함..
- right (왼쪽으로 이동하면서 블록 오른쪽으로 당기기 처리)
- 해당 블록들을 오른쪽으로 이동시켜야 하므로 열단위로 움직이면서 맨 오른쪽 열부터 왼쪽로 탐색하면서 오른쪽으로 이동시킬 수 있도록 구현하였다.
- 만약 왼쪽으로 이동하다가 숫자가 있는데 자기 자신과 같고 합쳐진 적이 없는 블록이라면 자기 자신에 그 블록이 합쳐지고 해당 부분은 0으로 처리한 후, 나의 블록에 방문처리(합쳐짐 체크) 해준다.
- 만약 열을 살피는 기준인 현재 열이 비어있는데 왼쪽으로 탐색하다가 숫자가 있으면 현재 내가 있는 열에 해당 값을 넣어주고 기존 열 부분에 0으로 처리하면서 블록을 오른쪽으로 이동시켜준다.
- 블록의 이동이 존재하면 카운트 시켜주는데 계속 돌면서 만약 블록의 이동처리가 끝나면(카운트=0)이면 해당 행의 모든 열 블록들은 이동처리가 끝난 것이다.
- 이런 카운트를 하는 이유가 한번 모든 열에서 오른쪽으로 블록이 만약 합쳐진 것이 있거나 블록의 이동이 있으면 중간에 상태가 변경되므로 다시 돌면서 이동처리 해줘야함..
💻 소스코드 - 1
// BOJ - 2048(Easy) (12100번)
// 구현 + DFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_12100_1 {
public static int n;
public static int ans_max;
public static int[] dx = {-1, 1, 0, 0};
public static int[] dy = {0, 0, -1, 1};
public static int[][] board;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board= new int[n][n];
StringTokenizer st = null;
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j=0;j<n;j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
ans_max = 0;
permutation(new int[5], 0);
System.out.println(ans_max);
}
public static void permutation(int[] arr, int depth) {
if(depth == 5) {
int[] arr_copy = arr.clone();
int[][] map_copy = new int[n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
map_copy[i][j] = board[i][j];
}
}
for(int i=0;i<5;i++) {
int dir = arr_copy[i];
if(dir == 0) {
up(map_copy);
} else if(dir == 1) {
down(map_copy);
} else if(dir == 2) {
left(map_copy);
} else {
right(map_copy);
}
int max_value = 0;
for(int p=0;p<n;p++) {
for(int q=0;q<n;q++) {
max_value = Math.max(max_value, map_copy[p][q]);
}
}
ans_max = Math.max(ans_max, max_value);
}
return;
}
for(int i=0;i<4;i++) {
arr[depth] = i;
permutation(arr, depth+1);
}
}
public static void up(int[][] map) {
boolean[][] visited = new boolean[n][n];
for(int j=0;j<n;j++) {
while(true) {
int cnt = 0;
int x = 0;
int nx = x + dx[1];
while(true) {
if(nx >= n) break;
if(map[nx][j] != 0 && !visited[x][j] && !visited[nx][j] && map[nx][j] == map[x][j]) {
map[x][j] += map[nx][j];
visited[x][j] = true;
map[nx][j] = 0;
cnt++;
} else if(map[x][j] == 0 && map[nx][j] != 0) {
map[x][j] = map[nx][j];
map[nx][j] = 0;
visited[x][j] = visited[nx][j];
visited[nx][j] = false;
cnt++;
}
x = nx;
nx += dx[1];
}
if(cnt == 0) {
break;
}
}
}
}
public static void down(int[][] map) {
boolean[][] visited = new boolean[n][n];
for(int j=0;j<n;j++) {
while(true) {
int cnt = 0;
int x = n-1;
int nx = x + dx[0];
while(true) {
if(nx < 0) break;
if(map[nx][j] != 0 && !visited[x][j] && !visited[nx][j] && map[nx][j] == map[x][j]) {
map[x][j] += map[nx][j];
visited[x][j] = true;
map[nx][j] = 0;
cnt++;
} else if(map[x][j] == 0 && map[nx][j] != 0) {
map[x][j] = map[nx][j];
map[nx][j] = 0;
visited[x][j] = visited[nx][j];
visited[nx][j] = false;
cnt++;
}
x = nx;
nx += dx[0];
}
if(cnt == 0) {
break;
}
}
}
}
public static void left(int[][] map) {
boolean[][] visited = new boolean[n][n];
for(int i=0;i<n;i++) {
while(true) {
int cnt = 0;
int y = 0;
int ny = y + dy[3];
while(true) {
if(ny >= n) break;
if(map[i][ny] != 0 && !visited[i][y] && !visited[i][ny] && map[i][y] == map[i][ny]) {
map[i][y] += map[i][ny];
visited[i][y] = true;
map[i][ny] = 0;
cnt++;
} else if(map[i][y] == 0 && map[i][ny] != 0) {
map[i][y] = map[i][ny];
map[i][ny] = 0;
visited[i][y] = visited[i][ny];
visited[i][ny] = false;
cnt++;
}
y = ny;
ny += dy[3];
}
if(cnt ==0) {
break;
}
}
}
}
public static void right(int[][] map) {
boolean[][] visited = new boolean[n][n];
for(int i=0;i<n;i++) {
while(true) {
int cnt = 0;
int y = n-1;
int ny = y + dy[2];
while(true) {
if(ny < 0) break;
if(map[i][ny] != 0 && !visited[i][y] && !visited[i][ny] && map[i][y] == map[i][ny]) {
map[i][y] += map[i][ny];
visited[i][y] = true;
map[i][ny] = 0;
cnt++;
} else if(map[i][y] == 0 && map[i][ny] != 0) {
map[i][y] = map[i][ny];
map[i][ny] = 0;
visited[i][y] = visited[i][ny];
visited[i][ny] = false;
cnt++;
}
y = ny;
ny += dy[2];
}
if(cnt ==0) {
break;
}
}
}
}
}📝 문제해결법 2
1. 이 문제는 BFS + 구현으로 풀이했다.
- BFS 내에서 큐안에 너비 단위로 4가지 방향으로 이동처리 (move 함수로) 한 후 최대값 갱신한다.
- 그리고 한 보드에 대해 5번까지 이동처리 가능하므로 5번이 이동처리를 끝냈다면 return 한다.
- 큐 안에서 이동 처리 전에 꼭 이전의 map 정보를 map_copy에 넣고 해당 보드를 이동 처리한다.
2. move 함수
- 방향(위쪽/왼쪽) - (동쪽/남쪽)으로 이동할 때 나누어서 처리한다.
- 방향 이동 처리 시에 만약 현재 칸이 빈칸이 아니라면 해당 방향으로 이동시킬 수 있을 때까지 계속 이동시키고 만약 이동할 곳에 자기자신과 같은 값이 있고 합쳐진 적이 없으면 합침처리하고, 만약 이동할 곳이 0으로 빈칸일 경우도 칸에 이동처리한다.
💻 소스코드 - 2
// BOJ - 2048(Easy) 12100번
// BFS + 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_12100_2 {
public static int n;
public static int ans_max;
// 북 - 동 - 남 - 서
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, 1, 0, -1};
public static int[][] board;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board= new int[n][n];
StringTokenizer st = null;
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j=0;j<n;j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
ans_max = 0;
bfs();
System.out.println(ans_max);
}
public static void move(int[][] map, int dir){
boolean[][] visited = new boolean[n][n];
int start = 0, end = 0, c = 0;
if(dir == 0 || dir == 3) {
start = 0;
end = n;
for(int j=start;j<end;j++) {
for(int i=start;i<end;i++) {
if(map[i][j] == 0) continue;
int x = i;
int y = j;
int temp = map[x][y];
map[x][y] = 0;
int nx = x + dx[dir];
int ny = y + dy[dir];
while(true) {
if(nx < 0 || ny < 0 || nx >= n || ny >= n) {
break;
}
if(map[nx][ny] == 0) {
x = nx;
y = ny;
nx = x + dx[dir];
ny = y + dy[dir];
} else if(!visited[nx][ny] && map[nx][ny] == temp) {
x = nx;
y = ny;
visited[nx][ny] = true;
break;
} else {
break;
}
}
map[x][y] += temp;
}
}
} else {
start = n-1;
end = -1;
for(int i=start;i>end;i--) {
for(int j=start;j>end;j--) {
if(map[i][j] == 0) continue;
int x = i;
int y = j;
int temp = map[x][y];
map[x][y] = 0;
int nx = x + dx[dir];
int ny = y + dy[dir];
while(true) {
if(nx < 0 || ny < 0 || nx >= n || ny >= n) {
break;
}
if(map[nx][ny] == 0) {
x = nx;
y = ny;
nx = x + dx[dir];
ny = y + dy[dir];
} else if(!visited[nx][ny] && map[nx][ny] == temp) {
x = nx;
y = ny;
visited[nx][ny] = true;
break;
} else {
break;
}
}
map[x][y] += temp;
}
}
}
}
public static void bfs() {
Queue<int[][]> q = new LinkedList<>();
q.offer(board);
int cnt = 0;
while(!q.isEmpty()) {
int q_len = q.size();
for(int l=0;l<q_len;l++) {
int[][] map = q.poll();
for(int d=0;d<4;d++) {
int[][] map_copy = new int[n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
map_copy[i][j] = map[i][j];
}
}
move(map_copy, d);
q.offer(map_copy);
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
ans_max = Math.max(ans_max, map_copy[i][j]);
}
}
}
}
cnt++;
if(cnt >= 5) {
return;
}
}
}
}'알고리즘 > 알고리즘문풀' 카테고리의 다른 글
| BOJ - 뱀 3190번 (JAVA) (0) | 2022.04.08 |
|---|---|
| BOJ - 연구소 14502번 (JAVA) (0) | 2022.04.08 |
| SWEA - 보급로 1249번 (JAVA) (0) | 2022.04.07 |
| BOJ - 정복자 14950번 (JAVA) (0) | 2022.03.17 |
| BOJ - 나만 안되는 연애 14621번 (JAVA) (0) | 2022.03.15 |