문제
내가 생각했을때 문제에서 원하는부분
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다.
0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다.
블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다.
블록은 적어도 하나 주어진다.
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.내가 이 문제를 보고 생각해본 부분
main : 보드 크기와 초기 상태를 입력받고, DFS 탐색을 시작한다.
dfs : 현재 이동 횟수(depth)가 5가 될 때까지 4가지 방향으로 이동한 결과를 재귀 탐색한다.
updateMax : 현재 보드에서 가장 큰 블록 값을 찾아 전역 변수 maxBlock과 비교하여 갱신한다.
move : 특정 방향으로 보드를 이동시키는 핵심 함수이다.
각 방향별로 줄 단위(행/열)에 대해 0 아닌 숫자를 순서대로 모아서 합병 가능한 블록은 합치고, 합병된 블록은 한 번만 합치게 처리한다.
이동 결과로 새 보드 배열을 반환한다.코드로 구현
package baekjoon.baekjoon_33;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 백준 12100번 문제
public class Main1326 {
static int N;
static int maxBlock = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] board = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(board, 0);
System.out.println(maxBlock);
br.close();
}
// 5회 이동 DFS 탐색
static void dfs(int[][] board, int depth) {
if (depth == 5) {
// 최대값 갱신
updateMax(board);
return;
}
for (int dir = 0; dir < 4; dir++) {
int[][] movedBoard = move(board, dir);
dfs(movedBoard, depth + 1);
}
}
// 최대 블록 값 갱신
static void updateMax(int[][] board) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
maxBlock = Math.max(maxBlock, board[i][j]);
}
}
}
// 방향에 따라 보드 이동(0:상, 1:하, 2:좌, 3:우)
static int[][] move(int[][] board, int dir) {
int[][] newBoard = new int[N][N];
// 깊은 복사
for (int i = 0; i < N; i++)
System.arraycopy(board[i], 0, newBoard[i], 0, N);
switch (dir) {
case 0: // 상
for (int col = 0; col < N; col++) {
int[] temp = new int[N];
boolean[] merged = new boolean[N];
int idx = 0;
for (int row = 0; row < N; row++) {
if (newBoard[row][col] != 0) {
int current = newBoard[row][col];
newBoard[row][col] = 0;
if (idx > 0 && temp[idx - 1] == current && !merged[idx - 1]) {
temp[idx - 1] *= 2;
merged[idx - 1] = true;
} else {
temp[idx++] = current;
}
}
}
for (int row = 0; row < N; row++) {
newBoard[row][col] = temp[row];
}
}
break;
case 1: // 하
for (int col = 0; col < N; col++) {
int[] temp = new int[N];
boolean[] merged = new boolean[N];
int idx = N - 1;
for (int row = N - 1; row >= 0; row--) {
if (newBoard[row][col] != 0) {
int current = newBoard[row][col];
newBoard[row][col] = 0;
if (idx < N - 1 && temp[idx + 1] == current && !merged[idx + 1]) {
temp[idx + 1] *= 2;
merged[idx + 1] = true;
} else {
temp[idx--] = current;
}
}
}
for (int row = 0; row < N; row++) {
newBoard[row][col] = temp[row];
}
}
break;
case 2: // 좌
for (int row = 0; row < N; row++) {
int[] temp = new int[N];
boolean[] merged = new boolean[N];
int idx = 0;
for (int col = 0; col < N; col++) {
if (newBoard[row][col] != 0) {
int current = newBoard[row][col];
newBoard[row][col] = 0;
if (idx > 0 && temp[idx - 1] == current && !merged[idx - 1]) {
temp[idx - 1] *= 2;
merged[idx - 1] = true;
} else {
temp[idx++] = current;
}
}
}
for (int col = 0; col < N; col++) {
newBoard[row][col] = temp[col];
}
}
break;
case 3: // 우
for (int row = 0; row < N; row++) {
int[] temp = new int[N];
boolean[] merged = new boolean[N];
int idx = N - 1;
for (int col = N - 1; col >= 0; col--) {
if (newBoard[row][col] != 0) {
int current = newBoard[row][col];
newBoard[row][col] = 0;
if (idx < N - 1 && temp[idx + 1] == current && !merged[idx + 1]) {
temp[idx + 1] *= 2;
merged[idx + 1] = true;
} else {
temp[idx--] = current;
}
}
}
for (int col = 0; col < N; col++) {
newBoard[row][col] = temp[col];
}
}
break;
}
return newBoard;
}
}
마무리
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.
Junior backend developer