본문 바로가기

카테고리 없음

[백준 12100번] 2048 (Easy) (Python3)

굉장히 까다로웠던 문제

골드 1인 구슬탈출이 훨씬 쉬운거같은데 왜 골2?

 

처음에는 아무생각없이 이렇게 코드를 짰다.

import sys
input = sys.stdin.readline
from copy import deepcopy
dy = [1,-1,0,0]
dx = [0,0,1,-1]

N = int(input())

board = []
for i in range(N):
  board.append(list(map(int,input().split())))

def move(y,x,direction,copyboard):
  num = copyboard[y][x]
  copyboard[y][x] = 0
  while True:
    y1 = y+dy[direction]
    x1 = x+dx[direction]
    if not (N>y1>=0 and N>x1>=0):
      break
    if copyboard[y1][x1] == num:
      copyboard[y1][x1] = num*2
      return
    if copyboard[y1][x1] != 0:
      break
    y,x = y1,x1
  copyboard[y][x] = num

def moveall(board,direction):
  copyboard = deepcopy(board)
  if direction == 1 or direction == 2:
    for i in range(N):
      for j in range(N):
        if copyboard[i][j] != 0:
          move(i,j,direction,copyboard)
  else:
    for i in reversed(range(N)):
      for j in reversed(range(N)):
        if copyboard[i][j] != 0:
          move(i,j,direction,copyboard)
  return copyboard

finish = False
maxnum = 2
def check(board):
  global finish,maxnum
  SUM = 0
  for i in range(N):
    for j in range(N):
      if board[i][j] != 0:
        maxnum = max(maxnum,board[i][j])
        SUM += board[i][j]
  if SUM < maxnum*2:
    finish = True

def game(board,cnt):
  if finish:
    return
  if cnt == 5:
    check(board)
    return
  for direction in range(4):
    game(moveall(board,direction),cnt+1)

game(board,0)

print(maxnum)

move함수를 만들어 모든 숫자를 제일 위에서부터 차례대로 방향대로 옮기고, 같은 숫자가 있으면 합쳐주는 방식이었다.

그러나 이 방식의 치명적인 문제점이 있었으니 바로 한번에 두번 합체하면 안된다는 것을 어겼다는 것이다.

 

즉 2 2 4 0을 왼쪽으로 옮길 경우, 4 4 0 0 이 되어야하는데, 내 방식은 8 0 0 0 이 되는 것이었다.

 

이걸 어떻게 구현해야할지 고민하다가 deque를 이용하기로 했다.

deque에 일렬로 문자를 쭉 담은 다음 뱉어내는 방식이다. 

 

코드는 아래와 같다.

import sys
input = sys.stdin.readline
from copy import deepcopy
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]

N = int(input())

board = []
for i in range(N):
  board.append(list(map(int,input().split())))

def move(board,direction):
  copyboard = deepcopy(board)
  for n in range(N):
    dq = deque()
    if direction == 0 or direction == 1:
      for i in range(N):
        if copyboard[i][n] != 0:
          dq.append(copyboard[i][n])
          copyboard[i][n] = 0
      if direction == 0:
        for i in reversed(range(N)):
          if not dq:
            break
          copyboard[i][n] = dq.pop()
          if not dq:
            break
          if copyboard[i][n] == dq[-1]:
            copyboard[i][n] *= 2
            dq.pop()
      else:
        for i in range(N):
          if not dq:
            break
          copyboard[i][n] = dq.popleft()
          if not dq:
            break
          if copyboard[i][n] == dq[0]:
            copyboard[i][n] *= 2
            dq.popleft()
    else:
      for i in range(N):
        if copyboard[n][i] != 0:
          dq.append(copyboard[n][i])
          copyboard[n][i] = 0
      if direction == 3:
        for i in reversed(range(N)):
          if not dq:
            break
          copyboard[n][i] = dq.pop()
          if not dq:
            break
          if copyboard[n][i] == dq[-1]:
            copyboard[n][i] *= 2
            dq.pop()
      else:
        for i in range(N):
          if not dq:
            break
          copyboard[n][i] = dq.popleft()
          if not dq:
            break
          if copyboard[n][i] == dq[0]:
            copyboard[n][i] *= 2
            dq.popleft()
  return copyboard
  
finish = False
maxnum = 2
def check(board):
  global finish,maxnum
  SUM = 0
  for i in range(N):
    for j in range(N):
      if board[i][j] != 0:
        maxnum = max(maxnum,board[i][j])
        SUM += board[i][j]
  if SUM < maxnum*2:
    finish = True

def game(board,cnt):
  if finish:
    return
  if cnt == 5:
    check(board)
    return
  for direction in range(4):
    game(move(board,direction),cnt+1)

game(board,0)

print(maxnum)

사실 구현방식의 문제이지 아이디어는 특별할게 없다.

 

move함수를 deque를 이용해 구현하였고, 매번 move할때마다 deepcopy를 한 뒤 return하는 전형적인 DFS 방식이다.

이때 시간을 줄이기 위해서 보드의 모든 수의 합이 가장 큰수의 두배보다 작을 경우 코드를 종료하도록 했는데, 효과가 있었는지는 잘 모르겠다.

 

 

오늘의 교훈) 문제를 꼼꼼이 읽자!