문제 링크 : https://www.acmicpc.net/problem/12100
코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!
문제 정의
- 보드의 크기 이 주어지고 다음 줄부터 의 입력이 주어짐
- 상/하/좌/우 이동 가능, 같은 숫자는 한 번만 병합 가능
- 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐짐
- 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력
위 그림과 같이 위로 이동할 경우 모든 블록이 위로 올라가며
같은 숫자는 합쳐지되 같은 수가 3개 있는 경우는 위쪽 칸에 합쳐졌습니다.
접근 방법
시간 복잡도
입력으로 주어지는 은 최대 20
따라서 보드의 최대 넓이는 400
이동 방향은 4방향,
5번 이동 가능하므로 경우의 수는 총 가지 입니다.
시간 복잡도는
이며
최대 연산 수는 회 입니다.
그러므로 어떤 최적화 방식을 사용하지 않더라도
구현을 하기만 한다면 문제를 해결할 수 있습니다.
플로우 정리
- 완전 탐색으로 상/하/좌/우 이동하고 이동 횟수 증가
- 이동 횟수가 5가 될 때 최댓값 갱신
여기서 필요한 메서드는 2가지 입니다.
- 상/하/좌/우로 모두 시뮬레이션하며
이동 횟수가 5일 때 최댓값 갱신하는bf메서드 - 상/하/좌/우로 이동하는 메서드
bf 메서드
static void bf(int n, int[][] board) {
if (n == 5) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
max = Math.max(max, board[i][j]);
}
}
return;
}
bf(n + 1, up(copyBoard(board)));
bf(n + 1, down(copyBoard(board)));
bf(n + 1, left(copyBoard(board)));
bf(n + 1, right(copyBoard(board)));
}브루트포스 코드는 다음과 같습니다.
n이 5인 경우- 최댓값인지 확인하고 최댓값인 경우 갱신
n이 5 이하인 경우- 이동 횟수
n을 증가 시키며 - 로직에 의해 상/하/좌/우로 이동한 보드를 다음 재귀로 넘기기
- 이동 횟수
이 때 상/하/좌/우로 이동하는 메서드들은 원본을 변경하기 때문에 깊은 복사를 한 배열을 활용합니다.
상/하/좌/우 메서드
pointer는i가 이동할 위치,i는 비교 대상이라 보시면 되겠습니다.
가장 먼저 pointer를 확인합니다.
pointer가 0인 경우i를 순회하면서 확인하고 0이 아닌 숫자가 나오는 순간pointer로 값을 이동
pointer가 0이 아닌 경우i를 순회하면서 확인하고 0이 아닌 숫자가 나오는 순간pointer와 비교- 이 때 같은 숫자면 합치고
pointer증가 - 다르다면
pointer증가 후 해당 위치에i의 숫자를 이동
- 이 때 같은 숫자면 합치고
나머지 하/좌/우 의 로직도 이와 동일하지만
pointer와 i의 인덱스에 주의하면서 구현해야 합니다.
예시
하나의 열에 대해서 up을 수행하는 예시를 들겠습니다.
현재와 같은 보드가 있고
pointer는 0의 위치
i는 1의 위치라고 가정하겠습니다.
비교했을 때 인덱스 i의 위치가 0이기에
i를 다음 인덱스로 이동합니다.
pointer는 이동하지 않아 0이고
다음 i는 2입니다.
pointer의 숫자와 i위치의 값이 같기 때문에
i의 숫자를 pointer로 합쳐서 pointer의 숫자가 4가 됩니다.
그 후 합쳐진 위치로는 더 이상 이동되지 않으므로
pointer의 인덱스를 증가시켜줍니다.
연산이 끝난 후의 보드는 다음과 같습니다.
pointer는 인덱스 1의 위치에, 값 0을 가리키고 있고
i는 인덱스 3의 위치에, 값 4를 가리키고 있습니다.
i의 값이 0이 아니고
pointer의 값이 0이기 때문에
i의 값을 pointer로 이동시킵니다.
아직 합쳐지지 않은 위치이기 때문에
아직은 이동 후보인 위치로서 pointer를 증가시키지 않습니다.
이후 i는 보드를 벗어나게 되므로
0열에 대한 up 로직이 종료됩니다.
이와 같은 연산을 모든 열에 대해 적용하게 되며
같은 로직이 네 방향으로 수행됩니다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N;
static int max = 0;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
int[][] board = new int[N][N];
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());
}
}
bf(0, board);
System.out.println(max);
}
static void bf(int n, int[][] board) {
if (n == 5) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
max = Math.max(max, board[i][j]);
}
}
return;
}
bf(n + 1, up(copyBoard(board)));
bf(n + 1, down(copyBoard(board)));
bf(n + 1, left(copyBoard(board)));
bf(n + 1, right(copyBoard(board)));
}
static int[][] copyBoard(int[][] board) {
int[][] copyBoard = new int[N][N];
for (int i = 0; i < N; i++){
copyBoard[i] = Arrays.copyOf(board[i], N);
}
return copyBoard;
}
static int[][] up (int[][] board) {
for (int j = 0; j < N; j++) {
int pointer = 0;
for (int i = 1; i < N; i++) {
if (board[i][j] == 0) continue;
int now = board[i][j];
board[i][j] = 0;
if (board[pointer][j] == 0) {
board[pointer][j] = now;
}
else {
if (board[pointer][j] == now) {
board[pointer][j] *= 2;
pointer++;
}
else {
pointer++;
board[pointer][j] = now;
}
}
}
}
return board;
}
static int[][] down (int[][] board) {
for (int j = 0; j < N; j++) {
int pointer = N-1;
for (int i = N-2; i >= 0; i--) {
if (board[i][j] == 0) continue;
int now = board[i][j];
board[i][j] = 0;
if (board[pointer][j] == 0) {
board[pointer][j] = now;
}
else {
if (board[pointer][j] == now) {
board[pointer][j] *= 2;
pointer--;
}
else {
pointer--;
board[pointer][j] = now;
}
}
}
}
return board;
}
static int[][] left (int[][] board) {
for (int i = 0; i < N; i++) {
int pointer = 0;
for (int j = 1; j < N; j++) {
if (board[i][j] == 0) continue;
int now = board[i][j];
board[i][j] = 0;
if (board[i][pointer] == 0) {
board[i][pointer] = now;
}
else {
if (board[i][pointer] == now) {
board[i][pointer] *= 2;
pointer++;
}
else {
pointer++;
board[i][pointer] = now;
}
}
}
}
return board;
}
static int[][] right (int[][] board) {
for (int i = 0; i < N; i++) {
int pointer = N-1;
for (int j = N-2; j >= 0; j--) {
if (board[i][j] == 0) continue;
int now = board[i][j];
board[i][j] = 0;
if (board[i][pointer] == 0) {
board[i][pointer] = now;
}
else {
if (board[i][pointer] == now) {
board[i][pointer] *= 2;
pointer--;
}
else {
pointer--;
board[i][pointer] = now;
}
}
}
}
return board;
}
}