[백준]2048 (Easy)

문제

https://www.acmicpc.net/problem/12100

풀이

1. 접근

• 해당 방법을 처음 보고 생각한건 dfs를 적용한 완전탐색 방법이었다. 한번의 시도당 위, 아래, 왼쪽, 오른쪽 총 4번의 시도가 있고 5번의 시도이므로 아무리 많아봐야 4^5이었기 때문이었다.

2. 숫자 밀기 + 합치기

• 예전 카카오 예제에서 인형뽑기 문제에서 풀었던 방법을 응용하면 될 것 같았다.
• {2,0,2,4} 라는 줄이 있으면(y축이든 x축이든 상관없이) 0을 제외하고 모두 스택에 거꾸로 넣은 후, 기존 줄을 모두 0으로 바꾸고 스택에서 하나씩 꺼내어 넣는 방법이다.
  • 예를 들면, 왼쪽으로 밀어넣을 때, 0을 제외한 수를 역순으로 스택에 넣으면 stack ={ 4,2,2}, 기존 ={0,0,0,0}이 된다. 여기서 스택에서 하나씩 넣으면 {4,2,2,0}이 되어 밀어넣어진다.
• 이 문제에서 추가적으로 2개의 수가 같으면 합쳐야하기 때문에 first_num과 second_num에 하나씩 넣고 둘을 비교하는 로직을 추가했다.
  1. stack ={4,2,2}, fisrt_num = None, second_num = None
  2. stack ={2,2} first_num =4, second_num = None
  3. if stack 이 true이므로 한번더 stack에서 pop하면
  4. stack={2}, first_num = 4, second_num =2
  5. first_num != second_num이므로 first_num만 그대로 기존 줄에 넣는다. second_num은 다시 stack에 넣는다. 기존 ={4,0,0,0}, stack ={2,2} first_num = None(이해하기 편의상), second_num = None
  6. 반복

3. 4개의 경우의 수

• 위, 아래, 왼, 오른쪽 각각의 경우에 따라 반복문 인덱스가 달라지기에 for문으로 4번 반복하게 했다.
• 또한 각각의 경우에 graph를 복사하여 다음 dfs에 넣어주었다.

코드

import sys
sys.setrecursionlimit(10**6)
n = int(input())
maps = []
for _ in range(n):
  maps.append(list(map(int, input().split())))
max_num = 0
move = [(1,0),(-1,0),(0,1),(0,-1)]
def make_queue(stack):
  queue = []
  while stack:
    f = stack.pop()
    if stack:
      s = stack.pop()
      if f == s:
        queue.append(f+s)
      else:
        queue.append(f)
        stack.append(s)
    else:
      queue.append(f)
  return queue

def dfs(maps, count):
  if count == 5:
    num = max(map(max,maps))
    global max_num
    max_num = max(max_num, num)
    return
  for dy, dx in move:
    stack = []
    queue = []
    if dx == 0:
      if dy == 1:
        graph= [y[:] for y in maps]
        for x in range(n):
          for y in range(n):
            if graph[y][x] != 0:
              stack.append(graph[y][x])
              graph[y][x] = 0
          queue = make_queue(stack)
          for i in range(len(queue)):
            graph[n-1-i][x] = queue[i]
        dfs(graph, count + 1)
      else:
        graph= [y[:] for y in maps]
        for x in range(n):
          for y in range(n-1,-1,-1):
            if graph[y][x] != 0:
              stack.append(graph[y][x])
              graph[y][x] = 0
          queue = make_queue(stack)
          for i in range(len(queue)):
            graph[i][x] = queue[i]
        dfs(graph, count + 1)
    else:
      if dx == 1:
        graph= [y[:] for y in maps]
        for y in range(n):
          for x in range(n):
            if graph[y][x] != 0:
              stack.append(graph[y][x])
              graph[y][x] = 0
          queue = make_queue(stack)
          for i in range(len(queue)):
            graph[y][n-i-1] = queue[i]
        dfs(graph, count + 1)            
      else:
        graph= [y[:] for y in maps]
        for y in range(n):
          for x in range(n-1,-1,-1):
            if graph[y][x] != 0:
              stack.append(graph[y][x])
              graph[y][x] = 0
          queue = make_queue(stack)
          for i in range(len(queue)):
            graph[y][i] = queue[i]
        dfs(graph, count + 1)            

dfs(maps, 0)
print(max_num)