[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
1️⃣ 서론
Kyun2da.github.io
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)