https://www.acmicpc.net/problem/12100
보드판 내의 전체 블록이 함께 이동한다. 이동 방향은 상, 하, 좌, 우이다.
이때 같은 값을 갖는 두 블록이 충돌하면 두 블록은 합쳐지게 된다.
단, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.
NxN 크기의 보드판에서 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값
보드판의 상태 관리가 필요하다.
각 블록을 관리를 할 텐데 해당 블록에는 값, 보드판에서의 위치, 그리고 이미 합쳐진 상태인지의 상태가 필요하다.
이동 방향 또한 중요한데 예를 들어 같은 값이 3개가 같은 열에 존재한다고 하자. 이 때 위쪽으로 이동하는 경우 위의 2개가 합쳐진다. 즉 위쪽에 가까운 것들이 먼저 합쳐진다.
또한 이동 횟수의 최댓값이 5로 정해져 있다.
백트랙킹 방법을 쓰면 될 것 같다.
백트랙킹의 탈출 조건이 뭘까 이동 횟수가 탈출 조건이 될 것이다. 이동 횟수가 5가 되면 최댓값을 갱신하고 탈출하면 된다.
또한 방문 처리를 해야 불필요한 반복을 하지 않는다. 하지만 이 방문을 어떤 기준으로 해야 할까?
그렇지만 이 방문 처리는 블록 내에 존재하는 모든 블록들을 통해 해야만 한다. N이 커질수록 블록의 개수가 NxN개가 되므로 곤란해진다.
최대 이동 횟수가 5회이기 때문에 방문처리를 안 하는 것도 방법일 수 있겠다.
그런데 블록을 어떻게 움직일 것인가.
- 그냥 각각의 블록들을 독립적으로 이동시켜 Queue에 쌓는다.
- 해당 Queue를 이동 거리에 따라 정렬한다.
- 앞에서부터 꺼낸다.
- 꺼내면서 값이 같으면 합치고 합쳐진 상태를 이전 것으로 기록한다.
- 다음 것을 꺼냈는데 이전 것과 같다면 이전것과 비교를 통해 합치거나 위치를 재정렬한다.
그런데 이 방법은 위치 조정이 복잡해질 것 같다. 또한 이전 블록과 비교해야 하는데 이거는 이동 방향에 따라 같은 열, 같은 행 등을 관리해줘야 한다.
따라서 그냥 블록을 이동방향에 따라 정렬하고 새로운 보드를 만들어 이동방향의 경계에 가까운 순서대로 배치해 나가자.
그런데 보드의 상태를 관리하는 클래스 내부에 보드판을 어떤 자료구조로 가지고 있어야 할까?
Block [][]과 int [][]의 선택지가 있다. Block의 경우 해당 위치에 블록의 병합 여부를 판단하기 쉬워지지만 객체를 제어해야 한다는 점에서 불편함이 늘어난다.
실수의 여지를 줄이기 위해 Block에서 병합 여부를 분리하고 별도의 boolean [][]을 사용해 관리하겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
public class Test {
static FastReader scan = new FastReader();
static int N;
static int[][] grid;
static int maxValue = Integer.MIN_VALUE;
static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 보드판의 상태
static class Board {
final int[][] board;
final List<Block> blocks;
final int maxValue;
final int moveCount;
public Board(int[][] board, List<Block> blocks, int maxValue, int moveCount) {
this.board = board;
this.blocks = blocks;
this.maxValue = maxValue;
this.moveCount = moveCount;
}
void printBoard(int[][] board) {
for (int[] row : board) {
System.out.println(Arrays.toString(row));
}
System.out.println();
}
Board move(int dir) {
//이동 방향을 전달받아 현재 보드판의 상태를 보고 이동시킨 후 새로운 보드판을 리턴
int[][] newBoard = new int[N][N];
boolean[][] merged = new boolean[N][N];
List<Block> sortedBlock = sortedBlockByDir(this.blocks, dir);
for (Block block : sortedBlock) {
Block movedBlock = moveBlock(block, dir, newBoard);
int r = movedBlock.r;
int c = movedBlock.c;
int value = movedBlock.value;
if (newBoard[r][c] != 0) {
// 이미 존재한다.
if (newBoard[r][c] == value && !merged[r][c]) {
// 값이 같은데 아직 병합이 안된 칸
newBoard[r][c] = value * 2;
merged[r][c] = true;
} else {
// 값이 다르거나 병합이 이미 됐거나 -> 위치 조정
newBoard[r - DIRECTION[dir][0]][c - DIRECTION[dir][1]] = value;
}
} else {
// 빈 공간
newBoard[r][c] = value;
}
}
// printBoard(newBoard);
// 새로운 보드가 완성된 상태
List<Block> newBlocks = new ArrayList<>();
int maxValue = this.maxValue;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (newBoard[i][j] == 0) {
continue;
}
maxValue = Math.max(maxValue, newBoard[i][j]);
Block block = new Block(i, j, newBoard[i][j]);
newBlocks.add(block);
}
}
return new Board(newBoard, newBlocks, maxValue, moveCount + 1);
}
private Block moveBlock(Block block, int dir, int[][] board) {
int r = block.r;
int c = block.c;
while (isValidPosition(r + DIRECTION[dir][0], c + DIRECTION[dir][1]) && board[r][c] == 0) {
r += DIRECTION[dir][0];
c += DIRECTION[dir][1];
}
return new Block(r, c, block.value);
}
private List<Block> sortedBlockByDir(List<Block> blocks, int dir) {
if (dir == 0) {
// 상 -> r오름차순
return blocks.stream().sorted(Comparator.comparingInt(block -> block.r)).collect(Collectors.toList());
} else if (dir == 1) {
// 하 -> r내림차순
return blocks.stream().sorted(Comparator.comparingInt(block -> -block.r)).collect(Collectors.toList());
} else if (dir == 2) {
// 좌 -> c오름차순
return blocks.stream().sorted(Comparator.comparingInt(block -> block.c)).collect(Collectors.toList());
} else {
// 우 -> c내림차순
return blocks.stream().sorted(Comparator.comparingInt(block -> -block.c)).collect(Collectors.toList());
}
}
private boolean isValidPosition(int r, int c) {
return r >= 0 && r < N && c >= 0 && c < N;
}
}
// 보드판 내 블록
static class Block {
final int r;
final int c;
final int value;
public Block(int r, int c, int value) {
this.r = r;
this.c = c;
this.value = value;
}
}
static void dfs(Board board) {
if (board.moveCount >= 5) {
maxValue = Math.max(maxValue, board.maxValue);
return;
}
for (int dir = 0; dir < 4; dir++) {
dfs(board.move(dir));
}
}
static void input() {
N = scan.nextInt();
grid = new int[N][N];
}
public static void main(String[] args) {
input();
List<Block> blocks = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] = scan.nextInt();
if (grid[i][j] == 0) {
continue;
}
maxValue = Math.max(grid[i][j], maxValue);
blocks.add(new Block(i, j, grid[i][j]));
}
}
Board board = new Board(grid, blocks, maxValue, 0);
dfs(board);
System.out.println(maxValue);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
'Algorithm > BOJ' 카테고리의 다른 글
| BOJ 14500 - 테트로미노 (1) | 2024.10.09 |
|---|---|
| BOJ 14499 - 주사위 굴리기 (1) | 2024.10.09 |
| BOJ 13458 - 시험 감독 (1) | 2024.10.09 |
| BOJ 3190- 뱀 (2) | 2024.10.08 |
| BOJ 13460 - 구슬탈출2 (0) | 2024.10.06 |