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

백준 12100번

✔ 문제 풀이

• 문제 자체는 그렇게 어렵지 않은 것 같기도 한데, 구현하는 부분에서 포인트를 한 두 개씩 놓치기 쉬운것 같다.

◼ 내가 놓쳤던 부분

1. 인접한 값들 말고도 합쳐질 수 있다는 점
   ⇒ 4 4 0 0 0의 경우 8 0 0 0 0으로 올바르게 합쳤으나
   ⇒ 4 0 0 0 4의 경우 왼쪽으로 합치면 8 0 0 0 0인데, 이를 합치지 않는 엄청난 실수 발생,,,

2. 합쳐지지 않아도 숫자가 이동할 수 있다는 점
   ⇒ 2 0 0 0 4의 경우 왼쪽으로 합칠 때 2 4 0 0 0이 되나 이를 구현하지 않음

• 알고리즘 문제 풀때는 문제 푸는데에 급급해져서 자꾸 기본적인 조건들을 놓치게된다..(ex. 카운트가 10을 넘어가면 -1을 출력하라고 돼있는데 이걸 안 읽어서 그냥 끝까지 탐색해서 출력하기 등..) 분명 문제에 써있는데...

• 아무튼!! 위의 것들만 신경 써주면 구현 자체는 크게 어렵지 않다.

.

◼ moveToDirection 함수 구현

• 정확한 표현은 sumUpToDirection인가..?
• moveToLeft와 moveToRight는 행방향(수평)으로 합치고, moveToUp와 moveToDown은 열방향(수직)으로 합친다.
• 함수에서 명시하는 방향으로부터 행렬을 탐색한다.(ex. moveToUp은 위쪽부터 열방향으로)
  .
• 열방향으로 탐색하는 경우,array[row][col]에서 row의 값을 증감하며 값들을 합친다.
  1) 탐색하고 있는 원소의 값이 0이 아니면서, array[row][col]와 다른 경우 값을 합치지 않는다.
  2) 탐색하고 있는 원소의 값이 array[row][col]와 같으면 array[row][col]의 값을 2배해주고, 탐색중이었던 원소는 0으로 변경한다
  ※ 나 자신은 탐색 대상에서 제외한다
  .
• 값들을 다 합쳐준 후, 합치는 방향으로 값들을 정렬한다
• 즉, 합치는 방향을 기준으로 값들 사이에 0이 있을 경우 이를 제거한다.
  1) 합치는 방향으로 배열을 탐색하면서 0이 있는 자리의 인덱스를 저장
  2) 탐색하는 원소가 0이 아닌데, 지나온 경로에 0이 존재할 경우 zero_index에서 popFront하여 해당하는 위치에 탐색하는 원소를 저장해주고, 원래 값이 있던 자리는 0으로 바꿔준다.
  .
• 원래는 위와 같은 방식으로 상하좌우에 해당하는 함수 4개를 작성했으나, 상&하, 좌&우는 탐색 방향의 차이만 있을뿐 로직의 차이는 없으므로, 함수를 하나로 합쳐 start, end, step을 인수로 받아 실행하도록 했다.

.

◼ dfs 함수 구현

• 더한 횟수를 저장하기 위한 전역 변수 max_value 선언
• 인수로 받은 depth가 5가 되는 순간, 배열 내의 최고값 원소를 탐색하여 max_value 값 업데이트
• 상하좌우에 대해 dfs를 재귀호출한다.
• 이때, 원본 배열을 변경하면 다른 분기에도 영향을 미침으로 배열을 deepcopy하여 인수로 전달한다.

.

최종 제출 코드

import copy

n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
max_value = 0
l = len(matrix)

def moveUpDown(array, start, end, step):

  for j in range(len(array[0])):
    for i in range(start, end, step):
      if not array[i][j]: continue
      for k in range(i, end, step):
        if k==i: continue
        if array[k][j] and array[k][j] != array[i][j]:
          break
        if array[i][j] == array[k][j]:
          array[i][j] += array[k][j]
          array[k][j] = 0
          break

  for j in range(len(array[0])):
    zero_index = []
    for i in range(start, end, step):
      if array[i][j] and zero_index:
        row = zero_index.pop(0)
        array[row][j] = array[i][j]
        array[i][j] = 0
      if array[i][j] == 0:
        zero_index.append(i)

  return array


def moveLeftRight(array, start, end, step):

  for i in range(len(array)):
    for j in range(start, end, step):
      if not array[i][j]: continue
      for k in range(j, end, step):
        if k==j: continue
        if array[i][k] and array[i][j] != array[i][k]:
          break
        if array[i][j] == array[i][k]:
          array[i][j] += array[i][k]
          array[i][k] = 0
          break

  for i in range(len(array)):
    zero_index = []
    for j in range(start, end, step):
      if array[i][j] and zero_index:
        col = zero_index.pop(0)
        array[i][col] = array[i][j]
        array[i][j] = 0
      if array[i][j] == 0:
        zero_index.append(j)

  return array



def getMaxValue(array):
  result = 0
  for i in range(len(array)):
    result = max(result, max(array[i]))
  return result



def dfs(lists, depth):

  global max_value

  if depth == 5:
    max_value = max(max_value, getMaxValue(lists))
    return

  dfs(moveUpDown(copy.deepcopy(lists), 0, l, 1), depth+1)
  dfs(moveUpDown(copy.deepcopy(lists), l-1, -1, -1), depth+1)
  dfs(moveLeftRight(copy.deepcopy(lists), 0, l, 1), depth+1)
  dfs(moveLeftRight(copy.deepcopy(lists), l-1, -1, -1), depth+1)

dfs(matrix, 0)
print(max_value)

.

◼ 궁금증

❓ zero_index를 deque로 구현하였을 때 오히려 실행시간이 오래 걸림... 도대체 why

• popleft 할 일이 많이 없어서 실행시간에 차이가 많이 없음 ⇒ 납득 가능
• 더 오래 걸림 ⇒ ...?