12100 swift / c++ - 2048 (Easy)

문제 개요는 2048게임을 구현하는 것.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

접근 방법. 4방향으로 합치고, 미는 dfs의 방법을 통해. 5번 할 수 있는 모든 방법을 찾아낸 뒤. 최대값으로 출력.

 

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 12100                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: chanhihi <boj.kr/u/chanhihi>                +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/12100                          #+#        #+#      #+#    */
/*   Solved: 2024/09/22 22:22:12 by chanhihi      ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */

#include <iostream>
#include <vector>

using namespace std;

int n;
int maxNumber = 0;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void move(int x, int y, int dir, vector<vector<int> > &board) {
  while (y + dy[dir] < n && x + dx[dir] < n && x + dx[dir] >= 0 &&
         y + dy[dir] >= 0) {
    if (board[y + dy[dir]][x + dx[dir]] == board[y][x]) {
      board[y + dy[dir]][x + dx[dir]] = board[y][x] * 2;
      board[y][x] = 0;

      maxNumber = max(maxNumber, board[y + dy[dir]][x + dx[dir]]);
    } else if (board[y + dy[dir]][x + dx[dir]] == 0) {
      board[y + dy[dir]][x + dx[dir]] = board[y][x];
      board[y][x] = 0;
    }
    x += dx[dir];
    y += dy[dir];
  }
}

void dfs(vector<vector<int> > board, int depth, int dir) {
  if (depth == 6) {
    return;
  }

  if (dir == 1 || dir == 2) {
    for (int y = 0; y < n; y++) {
      for (int x = 0; x < n; x++) {
        if (board[y][x] != 0) {
          move(x, y, dir, board);
        }
      }
    }
  } else if (dir == 0 || dir == 3) {
    for (int y = n - 1; y >= 0; y--) {
      for (int x = n - 1; x >= 0; x--) {
        if (board[y][x] != 0) {
          move(x, y, dir, board);
        }
      }
    }
  }

  for (int i = 0; i < 4; i++) {
    dfs(board, depth + 1, i);
  }
}

int main() {
  cin >> n;
  vector<vector<int> > board(n, vector<int>(n));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> board[i][j];
      maxNumber = max(maxNumber, board[i][j]);
    }
  }

  dfs(board, 0, 4);
  cout << maxNumber << endl;

  return 0;
}

첫 실패 원인을 알아보니 한 라인을 중복으로 합치고 밀고 있었음 ex) 2 2 2 2 2 2 -> 4 0 4 0 4 0 -> 4 0 8 0 0 0 이런식으로 합치고 밀고 하고있었음. 그래서 합치고 미는 코드를 짜보니, 4군데 전부 해야하기 때문에 미는 dir, 합치는 dir이 달라져야 해서 코드 난독화가 발생.

그래서 board를 돌리면서 한 군데에서 밀고 합치는 코드를 작성하기로 함.

C++ 문제풀이

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 12100                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: chanhihi <boj.kr/u/chanhihi>                +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/12100                          #+#        #+#      #+#    */
/*   Solved: 2024/09/22 22:22:12 by chanhihi      ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int n;
int maxNumber = 0;

vector<int> cleanUP(vector<int> newLine, vector<int> oldLine) {
  int index = 0;

  for (int i = 0; i < n; i++) {
    if (oldLine[i] != 0) {
      newLine[index++] = oldLine[i];
    }
  }

  return newLine;
}

void addNumber(vector<int>& line) {
  for (int i = 0; i < n - 1; i++) {
    if (line[i] == line[i + 1] && line[i] != 0) {
      line[i] *= 2;
      line[i + 1] = 0;
      maxNumber = max(maxNumber, line[i]);
    }
  }
}

vector<int> mergeLine(vector<int> line) {
  vector<int> newLine(n, 0);
  newLine = cleanUP(newLine, line);
  addNumber(newLine);
  vector<int> finalLine(n, 0);
  return cleanUP(finalLine, newLine);
}

vector<vector<int>> moveLeft(vector<vector<int>> board) {
  for (int i = 0; i < n; i++) {
    board[i] = mergeLine(board[i]);
  }
  return board;
}

vector<vector<int>> rotateClockwise(vector<vector<int>> board) {
  vector<vector<int>> newBoard(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      newBoard[j][n - 1 - i] = board[i][j];
    }
  }
  return newBoard;
}

void dfs(vector<vector<int>> board, int depth) {
  if (depth == 5) return;

  for (int i = 0; i < 4; i++) {
    vector<vector<int>> newBoard = moveLeft(board);
    dfs(newBoard, depth + 1);
    board = rotateClockwise(board);
  }
}

int main() {
  cin >> n;
  vector<vector<int>> board(n, vector<int>(n));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> board[i][j];
      maxNumber = max(maxNumber, board[i][j]);
    }
  }

  dfs(board, 0);

  cout << maxNumber << endl;

  return 0;
}

 

Swift 문제 풀이.

import Foundation

let n = Int(readLine()!)!
var board = [[Int]]()
var maxNumber = 0

for _ in 0..<n {
    let inputLine = readLine()!.split{$0==" "}.map { Int(String($0))! }
    board.append(inputLine)
    maxNumber = max(maxNumber, inputLine.max()!)
}

dfs(board, 0)

print(maxNumber)

func cleanUP(_ line: [Int]) -> [Int] {
    var newLine = [Int]()
    for num in line where num != 0 {
        newLine.append(num)
    }
    while newLine.count < n {
        newLine.append(0)
    }
    return newLine
}

func addNumber(_ line: inout [Int]) {
    for i in 0..<n - 1 {
        if line[i] == line[i + 1] && line[i] != 0 {
            line[i] *= 2
            line[i + 1] = 0
            maxNumber = max(maxNumber, line[i])
        }
    }
}

func mergeLine(_ line: [Int]) -> [Int] {
    var newLine = cleanUP(line)
    addNumber(&newLine)
    return cleanUP(newLine)
}

func moveLeft(_ board: [[Int]]) -> [[Int]] {
    var newBoard = board
    for i in 0..<n {
        newBoard[i] = mergeLine(board[i])
    }
    return newBoard
}

func rotateClockwise(_ board: [[Int]]) -> [[Int]] {
    var newBoard = Array(repeating: Array(repeating: 0, count: n), count: n)
    for i in 0..<n {
        for j in 0..<n {
            newBoard[j][n - 1 - i] = board[i][j]
        }
    }
    return newBoard
}

func dfs(_ board: [[Int]], _ depth: Int) {
    if depth == 5 { return }
    var board = board
    
    for _ in 0..<4 {
        let newBoard = moveLeft(board)
        dfs(newBoard, depth + 1)
        board = rotateClockwise(board)
    }
}