[백준_2048] (Easy).java

2024. 4. 7. 00:13·알고리즘/문제풀이
목차
  1. 목차
  2. 문제 해석
  3. 사고 과정
  4. 코드 구현
  5. 회고록

목차

  1. 문제 해석
  2. 사고 과정
  3. 코드 구현
  4. 회고록

문제 해석

문제에서 의미하는 단어들을 명확히 하는 단계입니다

2048 게임은 4 X 4 크기의 보드에서 즐기는 게임
한 번의 이동은 보드 위 전체블록을 상하좌우 중 하나로 이동
같은 값 두 블록 충돌 -> 하나로 합쳐짐
단 한 번의 이동에서 합쳐진 블록은 다시 합쳐짐 X
(블록 추가 X)
블록은 적어도 하나가 주어진다.

충돌의 의미?
같은 값을 갖는 두 블록 충돌 -> 합쳐진다.
세개 붙어있으면, 이동하려는 쪽으로 부터 가까운애들이 먼저 합쳐진다.

5번 이동해서 만들 수 있는 가장 큰 블록의 값?

 


사고 과정

5번 이동, 상하좌우 랜덤하게 모든 경우의 수 구해서 최댓값 갱신하는 형태
-> 5번 이동 후 최대값 조사 -> 재귀적 구현 + 이전 게임보드의 값을 저장해둬야함


충돌의 우선순위 파악
-> 이동 방향 기준으로 가까운 쪽부터 같은 것이 있는 지 조사

해당 지점이 0일 경우
-> 다음 충돌 가능성 조사

 


코드 구현

import java.util.Scanner;

public class EASY {
    static int Max, cnt;
    static int N;

    static int[][] board;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        Max = 0;
        board = new int[N][N];

        cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int num = sc.nextInt();
                board[i][j] = num;
            }
        }
        settle(0);
        System.out.println(Max);
    }

    //상하좌우에 따라 충돌 + 움직이는 메서드
    private static void settle(int circulation_num) {
        if (circulation_num >= 5) { //5개 돌았으면 됐어
            searchMax();
            return;
        }
        //가장 중요한 부분, 움직이기 전 게임판의 정보를 저장해두기
        int[][] copy = new int[N][N];
        for (int i = 0; i < N; i++)
            copy[i] = board[i].clone();

        for (int dir = 0; dir < 4; dir++) { //상우하좌
            game(dir);
            settle(circulation_num + 1);
            for (int i = 0; i < N; i++)
                board[i] = copy[i].clone();
            //게임 판을 이전걸로 돌려놔야돼

        }
    }


    private static void game(int dir) {

        move(dir); //먼저 해당 부분으로 다 옮긴 다음 충돌을 보자
        
        if (dir == 0) { //상
            for (int j = 0; j < N; j++) {//한 열씩 들어가보자
                for (int i = 0; i < N - 1; i++) { //한 행씩 볼거다
                    if (board[i][j] == 0) continue;

                    if (board[i + 1][j] == board[i][j]) {
                        int num1 = board[i][j];
                        board[i][j] = num1 + num1;
                        board[i + 1][j] = 0;
                    }
                }
            }
        } else if (dir == 1) { //우
            for (int i = 0; i < N; i++) {//한 열씩 들어가보자
                for (int j = N - 1; j > 0; j--) { //한 행씩 볼거다
                    if (board[i][j] == 0) continue;

                    if (board[i][j - 1] == board[i][j]) {
                        int num1 = board[i][j];
                        board[i][j] = num1 + num1;
                        board[i][j - 1] = 0;
                    }
                }
            }
        } else if (dir == 2) { //하
            for (int j = 0; j < N; j++) {//한 열씩 들어가보자
                for (int i = N - 1; i > 0; i--) { //한 행씩 볼거다
                    if (board[i][j] == 0) continue;

                    if (board[i - 1][j] == board[i][j]) {
                        int num1 = board[i][j];
                        board[i][j] = num1 + num1;
                        board[i - 1][j] = 0;
                    }
                }
            }
        } else if (dir == 3) { //좌
            for (int i = 0; i < N; i++) {//한 열씩 들어가보자
                for (int j = 0; j < N - 1; j++) { //한 행씩 볼거다
                    if (board[i][j] == 0) continue;
                    if (board[i][j + 1] == board[i][j]) {
                        int num1 = board[i][j];
                        board[i][j] = num1 + num1;
                        board[i][j + 1] = 0;
                    }
                }
            }
        }
        move(dir); // 0으로 채워진 부분이 있으니 이를 같은 방향으로 밀어서 마무리하기
    }

    private static void move(int dir) { //상우하좌
        if (dir == 0) { //상
            for (int c = 0; c < N; c++) {
                for (int r = 0; r < N; r++) {
                    if (board[r][c] == 0) {
                        int delta = 1;
                        while (r + delta < N) {
                            if (board[r + delta][c] == 0) {
                                delta++;
                                continue; // 또 0 만났으면 돌아가야지
                            }
                            if (board[r + delta][c] != 0) { //0 이 아니네!
                                board[r][c] = board[r + delta][c]; //자리 넣어주고
                                board[r + delta][c] = 0; //넌 0으로가라
                                break;
                            }
                        }
                    }
                }
            }
        } else if (dir == 1) { //우
            for (int r = 0; r < N; r++) {
                for (int c = N - 1; c >= 0; c--) {
                    if (board[r][c] == 0) {
                        int delta = 1;
                        while (c - delta >= 0) {
                            if (board[r][c - delta] == 0) {
                                delta++;
                                continue; // 또 0 만났으면
                            }
                            if (board[r][c - delta] != 0) { //0 이 아니네!
                                board[r][c] = board[r][c - delta]; //자리 넣어주고
                                board[r][c - delta] = 0; //넌 0으로가라
                                break;
                            }
                        }
                    }
                }
            }

        } else if (dir == 2) { //하
            for (int c = 0; c < N; c++) {
                for (int r = N - 1; r >= 0; r--) {
                    if (board[r][c] == 0) {
                        int delta = 1;
                        while (r - delta >= 0) {
                            if (board[r - delta][c] == 0) {
                                delta++;
                                continue; // 또 0 만났으면
                            }
                            if (board[r - delta][c] != 0) { //0 이 아니네!
                                board[r][c] = board[r - delta][c]; //자리 넣어주고
                                board[r - delta][c] = 0; //넌 0으로가라
                                break;
                            }
                        }
                    }
                }
            }
        } else if (dir == 3) {//좌
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (board[r][c] == 0) {
                        int delta = 1;
                        while (c + delta < N) {
                            if (board[r][c + delta] == 0) {
                                delta++;
                                continue; // 또 0 만났으면
                            }
                            if (board[r][c + delta] != 0) { //0 이 아니네!
                                board[r][c] = board[r][c + delta]; //자리 넣어주고
                                board[r][c + delta] = 0; //넌 0으로가라
                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    static void searchMax() { //최대값 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] > Max) {
                    Max = board[i][j];
                }
            }
        }
    }
}

회고록

  • 이전 게임판의 정보를 가져오는 과정에서 원활하게 생각하지 못했음

👉 단순히 재귀함수 for문 안에 이전 정보를 가져오는 것으로 처음엔 코드를 구현했으나, 이는 움직임 방향 순서가 (상, 상, 상, 우, 좌)에서 (상, 상, 상, 하, 상)으로 바뀔 경우, (상,상,상 )까지 게임 판의 정보를 가져오는 것이 아닌 직전의 순서인 (상, 상, 상, 우, 좌) 의 정보를 가져오며 의미없는 되돌리기 형태로 사용됨.

 

해당 스택 데이터 특성을 활용, copy 2차원 배열을 선언함으로써 해결

 

 

 

'알고리즘 > 문제풀이' 카테고리의 다른 글

프로그래머스_호텔 방 배정 <Java>  (1) 2024.10.13
[백준_14500] 테트로미노.java  (0) 2024.04.07
[백준_17471]게리맨더링.java  (0) 2024.04.05
[백준_15683] 감시.java  (0) 2024.04.03
[백준_14891] 톱니바퀴.java  (0) 2024.04.02
  1. 목차
  2. 문제 해석
  3. 사고 과정
  4. 코드 구현
  5. 회고록
'알고리즘/문제풀이' 카테고리의 다른 글
  • 프로그래머스_호텔 방 배정 <Java>
  • [백준_14500] 테트로미노.java
  • [백준_17471]게리맨더링.java
  • [백준_15683] 감시.java
지화자_
지화자_
나만의 글로 기록하기
지화자_
냉정과열정사이
지화자_
전체
오늘
어제
  • 분류 전체보기 (47)
    • 알고리즘 (18)
      • 개념정복 (6)
      • 문제풀이 (12)
    • ComputerScience (5)
      • 데이터베이스 (3)
      • 네트워크 (0)
      • OS (2)
    • SSAFY (2)
    • Java (6)
    • Server (10)
    • Spring (3)
    • 일상 (1)
    • OpenSource (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 나무섭지
  • AOP
  • BFS
  • dfs
  • 인터페이스
  • 부분집합
  • 백준바이러스
  • CI
  • 배포
  • 추상클래스
  • 분할정복
  • 백트래킹
  • 조합
  • 비트마스크
  • 아니안무서워
  • 재귀함수
  • n-queen
  • OOP
  • cd
  • 알고리즘
  • 소프티어
  • 백준
  • 구현
  • 빌드
  • 병합정렬

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
지화자_
[백준_2048] (Easy).java
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.