[DFS/BFS/완전탐색] ★★ 12100번 - 2048 (Easy)(DFS, 완전탐색)

[백준] 12100번 - 2048 (Easy)

풀이 시간: 6시간 이내

(한줄평) 내 설계대로 구현이 잘 되지 않아 다른 사람의 풀이를 참고했음에도 어려웠던 문제

상하좌우 이동 부분이 구현을 하기가 굉장히 까다로워 변수/조건이 조금만 달라져도 오류를 고치다 늪에 빠져버린... 추후 처음부터 끝까지 전체 코드를 직접 짜봐야할 문제!!

 

1) 문제 해결 아이디어

이 문제는 이동을 통해 변경된 정보를 담아둘 2차원 리스트(temp)를 깊은 복사를 통해 생성하는 것이 중요하다. 3번에서 1) move 함수로 2차원 리스트(temp)를 변경하고 2) dfs를 호출하고 3) 2차원 리스트(temp)를 원상복귀해준다 는 흐름이 중요하다!! 잊지말자 절대~~~

 

<dfs 동작 과정>

1. 깊이(depth)가 5이면 5번 이동했다는 것이므로 2차원 리스트(graph)에서 최댓값을 구한 후 그 값(block)과 기존 최댓값(max_block) 중 최댓값을 새로 구하여 최댓값을 갱신

2. 기존 보드(graph)를 temp에 깊은 복사

dfs 호출 후 바뀐 2차원 리스트를 원상복귀시켜주기 위해 원래 값을 담아놓아야 한다!!!

3. 상하좌우 4방향에 대해 반복 수행

3-1. 방향(d)와 보드 정보(temp)를 인자로 넘겨 move호출

3-2.  깊이(depth) + 1 한 값과 3-1에서 move로 바뀐 보드 정보(temp)를 인자로 넘겨 dfs 호출

3-3. dfs 호출 후에는 다시 원상복귀를 위해 사용할 보드 정보(temp)에 기존 보드 정보(graph)를 담음

 

<move 함수>

- 매개변수로 넘어온 방향(d)값에 따라 상/하/좌/우 로 이동하는 함수

이동의 동작과정을 이해하기 위해 아래와 같은 보드가 입력되었다고 가정한다.

여기서는 위쪽(0)으로 이동하는 것의 예시이다. 위쪽으로 이동하기 위해 각 열을 기준으로 1  ~ (n - 1)행에 대해 이동을 반복한다.

 

 

첫번째 오류. 틀렸습니다

이전값과 현재값이 다르면 앞에서 1) 0으로 바꿨던 현재값을 다시 원래대로 하고 2) 이전값 인덱스(idx)를 바꾸어야한다고 생각해서 아래 코드의 주석한 부분처럼 코드를 짰다.

나는 단순하게 위 그림의 0열에서 진행했던 3번의 경우처럼 idx, x가 붙어있을 경우만 생각했다. 하지만 실제로는 1열의 3번과 같이 idx, x가 떨어져있는 경우도 있다. 이러한 경우라면 현재값(4)는 현재값 인덱스(x)에 다시 쓰는게 아니라 이전값 인덱스 + 1(idx + 1)인 곳에 현재값을 넣어야 한다!!

  # 3. 이전 값과 현재값이 다르다면
  else:
    # 0으로 바꿨던 현재값을 원래대로 바꿈, 이전 값 바꿈
    #temp[x][y] = cur
    idx -= 1
    temp[x][idx] = cur

[참고] https://kyun2da.github.io/2020/09/26/2048easy/

[백준/Python] 12100 2048 (Easy) - Kyun2da Blog

 

2) 소스코드

from copy import deepcopy
import sys
input = sys.stdin.readline

# 방향에 따라 움직이는 함수
def move(d, temp):
  # 1. 위쪽으로 이동
  if d == 0:     
    # 한 열씩 위쪽으로 이동
    for y in range(n):  # 열
      idx = 0  # 이전 값(행) 인덱스
      for x in range(1, n):
        # 00. 현재값이 0이면 건너뛰기
        # 01. 현재 값이 0이 아니라면
        if temp[x][y]:
          # 현재값을 복사해 놓고 0으로 만듬
          cur = temp[x][y]   
          temp[x][y] = 0
          # 1. 이전 값이 0이라면
          if temp[idx][y] == 0:
            # 이전 값에 현재값을 대입, 이전 값은 그대로
            temp[idx][y] = cur
          # 2. 이전 값과 현재값이 같다면
          elif temp[idx][y] == cur:
            # 이전 값에 현재값을 더해줌, 이전 값 바꿈
            temp[idx][y] *= 2
            idx += 1           
          # 3. 이전 값과 현재값이 다르다면
          else:
            # 이전 값 바꿈, 이전 값에 현재값을 대입
            idx += 1
            temp[idx][y] = cur
  # 2. 아래쪽으로 이동
  elif d == 1:     
    # 한 열씩 아래쪽으로 이동
    for y in range(n):  # 열
      idx = n - 1  # 이전 값(행) 인덱스
      for x in range(n - 2, -1, -1):
        # 00. 현재값이 0이면 건너뛰기
        # 01. 현재 값이 0이 아니라면
        if temp[x][y]:
          # 현재값을 복사해 놓고 0으로 만듬
          cur = temp[x][y]   
          temp[x][y] = 0
          # 1. 이전 값이 0이라면
          if temp[idx][y] == 0:
            # 이전 값에 현재값을 대입, 이전 값은 그대로
            temp[idx][y] = cur
          # 2. 이전 값과 현재값이 같다면
          elif temp[idx][y] == cur:
            # 이전 값에 현재값을 더해줌, 이전 값 바꿈
            temp[idx][y] *= 2
            idx -= 1           
          # 3. 이전 값과 현재값이 다르다면
          else:
            # 이전 값 바꿈, 이전 값에 현재값을 대입
            idx -= 1
            temp[idx][y] = cur
  # 3. 왼쪽으로 이동
  elif d == 2:     
    # 한 행씩 왼쪽으로 이동
    for x in range(n):  # 행
      idx = 0  # 이전 값(열) 인덱스
      for y in range(1, n):
        # 00. 현재값이 0이면 건너뛰기
        # 01. 현재 값이 0이 아니라면
        if temp[x][y]:
          # 현재값을 복사해 놓고 0으로 만듬
          cur = temp[x][y]   
          temp[x][y] = 0
          # 1. 이전 값이 0이라면
          if temp[x][idx] == 0:
            # 이전 값에 현재값을 대입, 이전 값은 그대로
            temp[x][idx] = cur
          # 2. 이전 값과 현재값이 같다면
          elif temp[x][idx] == cur:
            # 이전 값에 현재값을 더해줌, 이전 값 바꿈
            temp[x][idx] *= 2
            idx += 1           
          # 3. 이전 값과 현재값이 다르다면
          else:
            # 이전 값 바꿈, 이전 값에 현재값을 대입
            idx += 1
            temp[x][idx] = cur
  # 4. 오른쪽으로 이동
  elif d == 3:     
    # 한 행씩 오른쪽으로 이동
    for x in range(n):  # 행
      idx = n - 1  # 이전 값(열) 인덱스
      for y in range(n - 2, -1, -1):
        # 00. 현재값이 0이면 건너뛰기
        # 01. 현재 값이 0이 아니라면
        if temp[x][y]:
          # 현재값을 복사해 놓고 0으로 만듬
          cur = temp[x][y]   
          temp[x][y] = 0
          # 1. 이전 값이 0이라면
          if temp[x][idx] == 0:
            # 이전 값에 현재값을 대입, 이전 값은 그대로
            temp[x][idx] = cur
          # 2. 이전 값과 현재값이 같다면
          elif temp[x][idx] == cur:
            # 이전 값에 현재값을 더해줌, 이전 값 바꿈
            temp[x][idx] *= 2
            idx -= 1           
          # 3. 이전 값과 현재값이 다르다면
          else:
            # 0으로 바꿨던 현재값을 원래대로 바꿈, 이전 값 바꿈
            idx -= 1
            temp[x][idx] = cur

# DFS
def dfs(depth, graph):
  global max_block
  # 5번 움직였으면 종료
  if depth == 5:
    block = max(map(max, graph))
    max_block = max(max_block, block)  # 최댓값 갱신
    return
  temp = deepcopy(graph)    # 기존 graph 깊은 복사
  # 이동할 방향 설정(중복 순열)에 따라 이동
  for d in range(4):
    move(d, temp)
    dfs(depth + 1, temp)
    temp = deepcopy(graph)
    
n = int(input())  # 보드 크기
# n * n(0: 빈칸)
graph = [list(map(int, input().split())) for _ in range(n)]
max_block = 0  # 블록의 최댓값
# 상, 하, 좌, 우
dx = [ -1, 1, 0, 0]
dy = [0, 0, -1, 1]

dfs(0, graph)
print(max_block)