[백준] #12100. 2480 (Easy)

문제는 여기서 확인할 수 있다. BaekJoon #12100. 2480 (Easy)

---

📌 POINT

1. 5번의 움직임 내에 최대 숫자를 확인한다.

2. 기울인 방향부터 합쳐진다. 합쳐진 칸은 또 합쳐지지 않는다.

3. 13460 문제와 비슷해보이지만 맵 전체의 상태를 저장해야 한다. => DFS 방식이 좋을듯

4. 주의할 점

• 기울인 방향부터 처리하는 것
• 원래 옆이 아닌데 기울이면서 붙을 수 있다는 점 확인하기 (삽질의 원인)

---

🚀 풀이

Ready

• 방향은 항상 헷갈린다. 방향은 인덱스로 미리 처리하되 미리 define해서 가독성을 높여둔다. (디버깅하는 미래의 나를 위하여...)

#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3

// move function
if(move_index == UP){ ... }
else if(move_index == DOWN){ ... }
else if(move_index == LEFT){ ... }
else { // RIGHT ... }

---

GO

1. 전체적인 DFS틀 만들기

1. move
2. board에서 최대값 구하기
3. 종료 조건
4. DFS 재귀 => 최대값 받아서 업데이트
5. 최종적으로 max 값 리턴

int max_2048(int n, int count_move, int move_index, vector<vector<int>> board){
    // move
    if(move_index >= 0){
        move(n, move_index, board);
    }
    // get max
    int max_num = get_max(n, board);
    if(count_move == 5) return max_num;

    // dfs
    for(int i=0; i<4; i++){
        int next_max = max_2048(n, count_move + 1, i, board);
        if(max_num < next_max) // update
            max_num = next_max;
    }
    
    return max_num;
}

2. move 함수 구현

• 라인별로 확인하기.
  확인하는 check_index와 새로 채워넣는 new_index 따로 선언
• 0 값은 무시
• 이전에 옮겼던 값을 prev에 저장

  prev와 같으면 : 합치고 prev = 0 초기화
  prev와 다르면 : prev를 밀어넣고 prev 업데이트

• 라인 확인이 끝나면

  prev가 있으면 마지막 칸에 밀어주기
  남은 자리에 0 채우기

void move(int n, int move_index, vector<vector<int>> &board){

    if(move_index == UP){
        for(int j=0; j<n; j++){
            int check_index = 0, new_index = 0;
            int prev = 0;

            for(; check_index<n; check_index++){
                if(board[check_index][j] == 0) continue;
                if(prev == 0) prev = board[check_index][j];
                else{
                    if(prev == board[check_index][j]){
                        // add
                        board[new_index++][j] = prev*2;
                        prev = 0;
                    }
                    else {
                        board[new_index++][j] = prev;
                        prev = board[check_index][j];
                    }
                }
            }
            if(prev != 0) board[new_index++][j] = prev;
            while(new_index < n) board[new_index++][j] = 0;
        }
    }
		else if(move_index == DOWN){ ... }
		else if(move_index == LEFT){ ... }
		else { // RIGHT ... }

		return;
}

---

전체 코드