[java,백준12100]2048 Easy - 브루트포스(BFS, DFS)로 최대값 찾기

BFS나 DFS(+백트래킹)로 시뮬레이션을 활용하여 2048 게임을 최대 5번 진행했을 때 얻을 수 있는 가장 큰 블록 값을 구하는 문제입니다.

2048 Easy(백준12100)

2048 이라는 게임을 이 링크에서 플레이해볼 수 있다.


헷갈리는 예시를 시각화 해보자

N=3
2 2 4    2 2 4    0 4 4
0 0 0 -> 0 0 0 -> 0 0 0
0 0 0    0 0 0    0 0 0
(초기)   (오른쪽)  (오른쪽)
즉, 오른쪽 때 0 0 8이 된다고 헷갈리지 말자.

2 2 4    4 0 4    4 4 0
0 0 0 -> 0 0 0 -> 0 0 0
0 0 0    0 0 0    0 0 0
(초기)   (왼쪽)    (왼쪽)
즉, 왼쪽 때 8 0 0이 된다고 헷갈리지 말자.



풀이

구현 시 주의사항

💡 DFS로 4방향 이동을 중복순열처럼 탐색+상태기록(백트래킹)+각 방향으로 이동 시뮬레이션방식으로 구현한다.
=> 움직일 때 마다 디버깅 추천!! (배열 출력해보아라)

💡 BFS는 상태기록(백트래킹) 없이 큐에 기록하는 차이가 전부이다.

💡 최대 5번이 전부이므로 복잡도는 신경 쓸 필요 없다.


핵심 구현 사항

  • DFS나 BFS를 통한 최대 5번의 이동 탐색!
  • 제일 중요한 구현사항
    1. 이동 방향의 블록 우선순위 처리
    2. 블록 합치기 처리 (이미 합친건 합치지 않기)
  • 각 상태에서 최대값 갱신!


블록 이동 처리(방향,좌표 설정)

static void move(int dir, Pair[][] board) {
    if (dir == 0) { // '->'
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                moveElement(i, N - 1 - j, board, dir);
            }
        }
    }else if (dir == 1) { // '아래'
    // ...
}


블록 이동 처리(while)

  1. nx<0 || ny<0 || nx>N-1 || ny>N-1 : 범위 초과 일 때 처리 -> 끝
  2. board[nx][ny].val == 0) : 빈 공간 일 때 처리 -> 블록 이동하려고
  3. board[nx][ny].val == board[x][y].val && !board[nx][ny].sum : 숫자가 같은 블록+이미 합친 적 있는 블록 일 때 처리 -> 블록 합치려고
  4. board[nxt] != board[nxt-1] : 숫자가 다른 블록 일 때 처리 -> 끝
static void moveElement(int x, int y, Pair[][] board, int dir) {
    int nx = x, ny = y;
    while (true) {
        nx += dx[dir];
        ny += dy[dir];
        if (nx < 0 || ny < 0 || nx >= N || ny >= N) break;
        // 이동 및 합치기 처리
        // ...
        x=nx;
	    y=ny; //이전 기록
    }
}



전체 코드 - BFS, DFS 둘 다

DFS 방식1

이미 합친 블록인지 체크: Pair 사용한 풀이

public class BOJ_2048Easy_12100 {
  static int N;
  static Pair[][] map;
  static int result;
  static int[] dx = {0, 1, 0, -1};
  static int[] dy = {1, 0, -1, 0};

  //방향 끝가지 이동 함수(while)
  static void moveElement(int x, int y, Pair[][] board, int dir) {
    int nx = x;
    int ny = y;
    while (true) {
      nx = dx[dir]+nx;
      ny = dy[dir]+ny;
      if(nx<0 || ny<0 || nx>N-1 || ny>N-1) break;
      if (board[nx][ny].val == 0) {
        board[nx][ny].val=board[x][y].val;
        board[nx][ny].sum=board[x][y].sum;
        board[x][y].val=0; board[x][y].sum=false;
      } else if (board[nx][ny].val == board[x][y].val && !board[nx][ny].sum) {
        board[nx][ny].val += board[x][y].val;
        board[nx][ny].sum = true;
        board[x][y].val=0; board[x][y].sum=false;
        break;
      } else { //board[nxt] != board[nxt-1]
        break;
      }
      x=nx;
      y=ny; //이전 기록
    }
  }
  //방향 끝까지 이동 함수(좌표설정)
  static void move(int dir, Pair[][] board) {
    if (dir == 0) { // '->'
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          moveElement(i, N - 1 - j, board, dir);
        }
      }
    }else if (dir == 1) { // '아래'
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          moveElement(N - 1 - j, i, board, dir);
        }
      }
    }else if (dir == 0) { // '<-'
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          moveElement(i, j, board, dir);
        }
      }
    }else { // '위'
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          moveElement(j, i, board, dir);
        }
      }
    }
  }

  static void dfs(int depth, Pair[][] board) {
    //base condition
    if (depth == 5) {
      int maxVal=0; //제일 큰 값
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          maxVal = Math.max(maxVal, board[i][j].val);
        }
      }
      result = Math.max(result, maxVal);
      return;
    }
    //recursion
    for (int i = 0; i < 4; i++) {
      Pair[][] copy = new Pair[N + 1][N + 1]; //항상 복제본을 넘겨야 그 당시의 상태값을 유지할 수 있다.
      for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
          copy[j][k]=new Pair(board[j][k].val, false); //false 로 init
        }
      } //간단한 복제면 clone 메소드 사용 추천
      move(i, copy); //게임시작
//      printAll(depth+1, copy, i); //debug
      dfs(depth + 1, copy);
    }
  }

  private static void printAll(int depth, Pair[][] copy, int dir) {
    System.out.println("depth:"+ depth);
    System.out.println("dir:"+ dir);
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        System.out.print(copy[i][j]+",");
      }
      System.out.println();
    }
    System.out.println();
  }

  public static void main(String[] args) throws IOException {
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    map = new Pair[N+1][N+1];
    for (int i = 0; i < N; i++) {
      StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
      for (int j = 0; j < N; j++) {
        map[i][j] = new Pair(Integer.parseInt(stk.nextToken()), false);
      }
    }
    //run
    dfs(0, map);
    //output
    System.out.println(result);
  }

  static class Pair {
    int val; boolean sum;

    public Pair(int val, boolean sum) {
      this.val=val; this.sum=sum;
    }

    @Override
    public String toString() {
      return "Pair{" +
          "val=" + val +
          ", sum=" + sum +
          '}';
    }
  }

}
/*
3
2 2 4
0 0 0
0 0 0

3
2 0 0
2 2 0
2 0 0

4
2 4 8 2
2 4 0 0
2 0 0 0
2 0 2 0
 */



DFS 방식2

이미 합친 블록인지 체크: flagMap[][] 사용한 풀이

import java.io.*;
import java.util.*;
public class 이공사팔_12100 {
  static final int MAX_COUNT = 5;
  static final int[] dx = {0, 1, 0, -1};
  static final int[] dy = {1, 0, -1, 0};
  static int N, result;
  static int[][] inArr;

  public static void moveElement(int x, int y, int dir, int[][] flagMap) {
    int nx = x; int ny = y;
    int init = inArr[x][y]; //초기값
    while (true) {
      nx += dx[dir];
      ny += dy[dir];
      //base condition -> 못 움직일 때 (범위 초과, 숫자 다른 블록, 이미 합친 블록)
      if(nx<0 || ny<0 || nx>=N || ny>=N) break;
      if(inArr[nx][ny] != 0 && init != inArr[nx][ny]) break;
      if(inArr[nx][ny] != 0 && init == inArr[nx][ny]
          && (flagMap[nx][ny] == 1 || flagMap[x][y] == 1)) break; //flag는 이동하는 블록과 이동할 위치의 블록 둘다 체크해야 한다.
      //while - update
      if (inArr[nx][ny] == 0) {
        inArr[nx][ny] = init;
      } else {
        //여기는 숫자 합치는 분기밖에 없음 -> 나머지 분기는 위에서 이미 처리
        inArr[nx][ny] = init*2;
        init = init*2; //init 도 update
        flagMap[nx][ny] = 1;
      }
      inArr[x][y] = 0;
      x = nx; y = ny;
    }
  }

  public static void move(int dir, int debug) {
    // 구현 - N*N 각 원소마다 적용 + 방향별 구분(방향쪽 원소부터 적용) + 이동은 끝까지(요소단위 while)
    int[][] flagMap = new int[N + 1][N + 1]; //N 작으니 매번 재할당 (초기값 0)
    for (int i = 0; i < N; i++) {
      if (dir == 0) { //오른쪽 -> 방향쪽 원소부터 적용 중요
        for (int j = N - 1; j >= 0; j--) {
          moveElement(i, j, dir, flagMap); // 끝까지 이동
        }
      } else if (dir == 1) { //아래쪽
        for (int j = N - 1; j >= 0; j--) {
          moveElement(j, i, dir, flagMap);
        }
      } else if (dir == 2) { //왼쪽
        for (int j = 0; j < N; j++) {
          moveElement(i, j, dir, flagMap);
        }
      } else { //dir == 4 (위쪽)
        for (int j = 0; j < N; j++) {
          moveElement(j, i, dir, flagMap);
        }
      }
    }
    //debug
//    System.out.println("방향:"+dir+" 깊이:"+debug);
//    for (int i = 0; i < N; i++) {
//      System.out.println(Arrays.toString(inArr[i]));
//    }
  }

  public static void dfs(int depth) {
    //base condition
    if (depth == MAX_COUNT) {
      int val = 0;
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          val = Math.max(val, inArr[i][j]);
        }
      }
      result = Math.max(val, result);
      return;
    }
    //recursion
    int copy[][] = new int[N + 1][N + 1]; // N 작으니 매번 재할당
    for(int i=0; i<N; i++) copy[i] = inArr[i].clone(); // 2차원 배열 복제
    for (int i = 0; i < 4; i++) {
      int dir = i; //방향
      move(dir, depth);
      dfs(depth + 1);
      for(int k=0; k<N; k++) inArr[k] = copy[k].clone(); //backtracking
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    inArr = new int[N+1][N+1];
    //input
    for (int i = 0; i < N; i++) {
      StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
      for (int j = 0; j < N; j++) {
        inArr[i][j] = Integer.parseInt(stk.nextToken());
      }
    }
    //debug
//    System.out.println("입력 값");
//    for (int i = 0; i < N; i++) {
//      System.out.println(Arrays.toString(inArr[i]));
//    }
    //run
    dfs(0);
    //output
    System.out.println(result);
  }

}



BFS 방식

이미 합친 블록인지 체크: Pair 사용한 풀이

public class BOJ_2048Easy_12100 {
  static int N;
  static Pair[][] map;
  static int result;
  static int[] dx = {0, 1, 0, -1};
  static int[] dy = {1, 0, -1, 0};

  //방향 끝가지 이동 함수(while)
  static void moveElement(int x, int y, Pair[][] board, int dir) {
    int nx = x;
    int ny = y;
    while (true) {
      nx = dx[dir]+nx;
      ny = dy[dir]+ny;
      if(nx<0 || ny<0 || nx>N-1 || ny>N-1) break;
      if (board[nx][ny].val == 0) {
        board[nx][ny].val=board[x][y].val;
        board[nx][ny].sum=board[x][y].sum;
        board[x][y].val=0; board[x][y].sum=false;
      } else if (board[nx][ny].val == board[x][y].val && !board[nx][ny].sum) {
        board[nx][ny].val += board[x][y].val;
        board[nx][ny].sum = true;
        board[x][y].val=0; board[x][y].sum=false;
        break;
      } else { //board[nxt] != board[nxt-1]
        break;
      }
      x=nx;
      y=ny; //이전 기록
    }
  }
  //방향 끝까지 이동 함수(좌표설정)
  static void move(int dir, Pair[][] board) {
    if (dir == 0) { // '->'
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          moveElement(i, N - 1 - j, board, dir);
        }
      }
    }else if (dir == 1) { // '아래'
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          moveElement(N - 1 - j, i, board, dir);
        }
      }
    }else if (dir == 0) { // '<-'
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          moveElement(i, j, board, dir);
        }
      }
    }else { // '위'
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          moveElement(j, i, board, dir);
        }
      }
    }
  }

  static void bfs(Pair[][] board) {
    Queue<Pair[][]> qu = new ArrayDeque<>();
    qu.offer(board);
    int level=0;
    while (!qu.isEmpty()) {
      int size = qu.size();
      level++;
      for (int s = 0; s < size; s++) {
        Pair[][] cur = qu.poll();
        for (int i = 0; i < 4; i++) {
          Pair[][] copy = new Pair[N + 1][N + 1]; //항상 복제본을 넘겨서 큐에 문제없이 담는다.
          for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
              copy[j][k]=new Pair(cur[j][k].val, false); //false 로 init
            }
          } //간단한 복제면 clone 메소드 사용 추천
          move(i, copy);
//          printAll(level, copy, i); //debug
          qu.offer(copy);
        }
      }
      //base condition
      if (level == 5) {
        while (!qu.isEmpty()) {
          int maxVal=0; //제일 큰 값
          Pair[][] cur = qu.poll();
          for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
              maxVal = Math.max(maxVal, cur[j][k].val);
            }
          }
          result = Math.max(result, maxVal);
        }
        break;
      }
    }

  }

  private static void printAll(int depth, Pair[][] copy, int dir) {
    System.out.println("depth:"+ depth);
    System.out.println("dir:"+ dir);
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        System.out.print(copy[i][j]+",");
      }
      System.out.println();
    }
    System.out.println();
  }

  public static void main(String[] args) throws IOException {
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    map = new Pair[N+1][N+1];
    for (int i = 0; i < N; i++) {
      StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
      for (int j = 0; j < N; j++) {
        map[i][j] = new Pair(Integer.parseInt(stk.nextToken()), false);
      }
    }
    //run
    bfs(map);
    //output
    System.out.println(result);
  }

  static class Pair {
    int val; boolean sum;

    public Pair(int val, boolean sum) {
      this.val=val; this.sum=sum;
    }

    @Override
    public String toString() {
      return "Pair{" +
          "val=" + val +
          ", sum=" + sum +
          '}';
    }
  }

}
/*
3
2 2 4
0 0 0
0 0 0

3
2 0 0
2 2 0
2 0 0

4
2 4 8 2
2 4 0 0
2 0 0 0
2 0 2 0
 */

주관적인 생각의 풀이이므로 틀린 부분 지적은 언제나 환영합니다⚡

댓글남기기

참고