백준 12100번 2048(Easy)

백준 12100번 2048(Easy)

문제 바로가기

코드

import sys

# 상하좌우에 따른 이동 함수 결정하기
def select(i, board_dfs):
  check = [[0 for _ in range(N)] for _ in range(N)]
  # 상
  if i == 0:
    for r in range(N):
      for c in range(N):
        if board_dfs[r][c] == 0:
          continue
        move(r, c, i, board_dfs, check)
  # 우 
  elif i == 1:
    for c in range(N):
      for r in range(N):
        if board_dfs[r][N-1-c] == 0:
          continue
        move(r, N-1-c, i, board_dfs, check)
  # 하
  elif i == 2:
    for r in range(N):
      for c in range(N):
        if board_dfs[N-1-r][c] == 0:
          continue
        move(N-1-r, c, i, board_dfs, check)
  # 좌  
  else:
    for c in range(N):
      for r in range(N):
        if board_dfs[r][c] == 0:
          continue
        move(r, c, i, board_dfs, check)

# 상하좌우에 따른 이동 함수
def move(r, c, direction, board_dfs, check):
  i = 0
  # 상
  if direction == 0:
    if r != 0:
      while r > i:
        i += 1
        if board_dfs[r-i][c] != 0:
          break    
      if board_dfs[r-i][c] == board_dfs[r][c] and check[r-i][c] == 0:
        board_dfs[r][c] = 0
        board_dfs[r-i][c] = board_dfs[r-i][c]*2
        check[r-i][c] = 1
      elif board_dfs[r-i][c] == 0:
        board_dfs[r-i][c] = board_dfs[r][c]
        board_dfs[r][c] = 0
      else:
        i -= 1
        if i > 0:
          board_dfs[r-i][c] = board_dfs[r][c]
          board_dfs[r][c] = 0
          check[r][c] = 0
  # 우
  elif direction == 1:
    if c != N-1:
      while c + i < N-1:
        i += 1
        if board_dfs[r][c+i] != 0:
          break    
      if board_dfs[r][c+i] == board_dfs[r][c] and check[r][c+i] == 0:
        board_dfs[r][c] = 0
        board_dfs[r][c+i] = board_dfs[r][c+i]*2
        check[r][c+i] = 1
      elif board_dfs[r][c+i] == 0:
        board_dfs[r][c+i] = board_dfs[r][c]
        board_dfs[r][c] = 0
      else:
        i -= 1
        if i > 0:
          board_dfs[r][c+i] = board_dfs[r][c]
          board_dfs[r][c] = 0
          check[r][c] = 0
  # 하
  elif direction == 2:
    if r != N-1:
      while r + i < N-1:
        i += 1
        if board_dfs[r+i][c] != 0:
          break    
      if board_dfs[r+i][c] == board_dfs[r][c] and check[r+i][c] == 0:
        board_dfs[r][c] = 0
        board_dfs[r+i][c] = board_dfs[r+i][c]*2
        check[r+i][c] = 1
      elif board_dfs[r+i][c] == 0:
        board_dfs[r+i][c] = board_dfs[r][c]
        board_dfs[r][c] = 0
      else:
        i -= 1
        if i > 0:
          board_dfs[r+i][c] = board_dfs[r][c]
          board_dfs[r][c] = 0
          check[r][c] = 0
  # 좌
  elif direction == 3:
    if c != 0:
      while c > i:
        i += 1
        if board_dfs[r][c-i] != 0:
          break    
      if board_dfs[r][c-i] == board_dfs[r][c] and check[r][c-i] == 0:
        board_dfs[r][c] = 0
        board_dfs[r][c-i] = board_dfs[r][c-i]*2
        check[r][c-i] = 1
      elif board_dfs[r][c-i] == 0:
        board_dfs[r][c-i]= board_dfs[r][c]
        board_dfs[r][c] = 0
      else:
        i -= 1
        if i > 0:
          board_dfs[r][c-i]= board_dfs[r][c]
          board_dfs[r][c] = 0
          check[r][c] = 0

# dfs를 통해서 모든 경우의 수 탐색
def dfs(board, depth):
  global answer
  # 5번의 이동을 끝마치면 최대값을 구하기
  if depth >= 6:
    result = 0
    for r in range(N):
      for c in range(N):
        result = max(result, board[r][c])
    answer = max(answer, result)

  else:
    for i in range(4):
      copy_board = [board[_][:] for _ in range(N)]
      select(i, copy_board)  
      dfs(copy_board, depth+1)

N = int(sys.stdin.readline())
board = []

for i in range(N):
  board.append(list(map(int, sys.stdin.readline().split())))

dy = [-1, 0, 1, 0] 
dx = [0, 1, 0, -1]

answer = 0
dfs(board, 1)
print(answer)

⁉️ 문제 풀이

구현문제

1. 상하좌우에 따라서 한번씩 움직이게 된다. 그러다가 5번을 움직이고 나면 남아있는 보드판의 최댓값을 구하는 문제이다.

2. 여기서 상하좌우로 움직일때 움직일 수 있는 최대로 움직이고 만약 자신과 같은 숫자를 만나게 된다면 2배로 합쳐지게 된다.

3. 그리고 한번의 움직임에서 이미 합쳐진 숫자들은 한번더 합쳐질 수 없다.

   이를 구현하기 위해서 check라는 배열을 통해서 합쳐진 숫자들을 구분했다.

모든 경우의 수 탐색

위와 같이 보드판을 5번을 움직인 다음 최대값을 구하는 문제이다.

이 문제는 총 횟수가 5번이며 DP를 이용해서 구하는 것이 도움이 되지 않을 것으로 판단하여 DFS 를 이용해서 모든 경우의 수를 한번씩 다 탐색하는 방법을 사용했다.

여기서 BFS를 이용하지 않은 것은 경우의 수 1개를 완전하게 탐색하고 다음 것을 진행하는 것이 아니기 때문에 보드판의 숫자들을 제어할 수 없을 것이라 판단했다.

📎 참고

도움이 되었던 반례

3
0 8 1024
4 0 4
0 1024 32
output: 1024
correct answer: 2048

3
256 8 128
16 0 256
0 8 0
output: 256
correct answer: 512

혹시 이 반례들이 틀린다면 DFS 를 통해서 각 경우의 수를 수행할 때 보드판의 숫자들이 제대로 초기화가 되는지 확인해보아야 할것이다.

2048 게임

2048 게임 플레이 해보기