2048 (Easy)
문제 링크 : https://www.acmicpc.net/problem/12100 (opens in a new tab)
내 풀이
일단 풀이 아이디어 자체가 어려운 문제는 아니었다. 그냥 Brute Force로 4방향을 5번씩 돌려서 총 1024번의 경우의 수를 다 돌려보면 된다.
시간 복잡도를 크게 고려할 필요는 없는 문제였던 것 같지만 내가 생각하지 못한건 dfs를 돌릴 경우 board를 매번 넘기더라도 하나의 dfs 펑션이 진행되는 동안 board가 stack에 있으므로 메모리 초과가 나지 않는다는 점과 각 방향으로 진행시키는 함수를 너무 무식하게 짯다는 점이다.
이런건 프로그래밍 센스의 문제인 것 같다.
from collections import deque
N = int(input())
graph = []
for _ in range(N) :
graph.append(list(map(int, input().split())))
def make_local_graph(v_hash) :
local_graph = [[] for _ in range(N)]
for r in range(N) :
for c in range(N) :
cur_key = f"{r}-{c}"
if cur_key in v_hash :
local_graph[r].append(v_hash[cur_key])
else :
local_graph[r].append(0)
return local_graph
def get_local_hash(graph) :
v_hash = {}
for r in range(N) :
for c in range(N) :
if graph[r][c] != 0 :
v_hash[f"{r}-{c}"] = graph[r][c]
return v_hash
def move_up(v_hash) :
lg = make_local_graph(v_hash = v_hash)
merged = [[False for _ in range(N)] for _ in range(N)]
for r in range(N) :
for c in range(N) :
nr = r
while True :
nr -= 1
if merged[nr][c] or nr == -1 : # 끝에 왔거나 합쳐지지 않을 경우
if nr+1 != r :
lg[nr+1][c] = lg[r][c]
lg[r][c] = 0
break
elif lg[nr][c] == lg[r][c] and not merged[nr][c] : # 합쳐질경우
lg[nr][c] *= 2
lg[r][c] = 0
merged[nr][c] = True
break
return get_local_hash(lg)
def move_down(v_hash) :
lg = make_local_graph(v_hash = v_hash)
merged = [[False for _ in range(N)] for _ in range(N)]
for r in range(N-1, -1, -1) :
for c in range(N) :
nr = r
while True :
nr += 1
if nr == N or merged[nr][c] or lg[nr][c] != lg[r][c] : # 끝에 왔거나 합쳐지지 않을 경우
if nr-1 != r :
lg[nr-1][c] = lg[r][c]
lg[r][c] = 0
break
elif lg[nr][c] == lg[r][c] and not merged[nr][c] : # 합쳐질경우
lg[nr][c] *= 2
lg[r][c] = 0
merged[nr][c] = True
break
return get_local_hash(lg)
def move_left(v_hash) :
lg = make_local_graph(v_hash = v_hash)
merged = [[False for _ in range(N)] for _ in range(N)]
for r in range(N) :
for c in range(N) :
nc = c
while True :
nc -= 1
if merged[r][nc] or nc == -1 or lg[r][nc] != lg[r][c] : # 끝에 왔거나 합쳐지지 않을 경우
if nc-1 != c :
lg[r][nc - 1] = lg[r][c]
lg[r][c] = 0
break
elif lg[r][nc] == lg[r][c] and not merged[r][nc] : # 합쳐질경우
lg[r][nc] *= 2
lg[r][c] = 0
merged[r][nc] = True
break
return get_local_hash(lg)
def move_right(v_hash) :
lg = make_local_graph(v_hash = v_hash)
merged = [[False for _ in range(N)] for _ in range(N)]
for r in range(N - 1, -1, -1) :
for c in range(N) :
nc = c
while True :
nc += 1
if nc == N or merged[r][nc] or lg[nc][]: # 끝에 왔거나 합쳐지지 않을 경우
if nc+1 != c :
lg[r][nc - 1] = lg[r][c]
lg[r][c] = 0
break
elif lg[r][nc] == lg[r][c] and not merged[r][nc] : # 합쳐질경우
lg[r][nc] *= 2
lg[r][c] = 0
merged[r][nc] = True
break
return get_local_hash(lg)
def main(graph) :
v_hash = get_local_hash(graph)
q = deque()
q.append([v_hash, 0])
max_value = 0
while q :
v_hash, cur_cnt = q.popleft()
if cur_cnt == 5 :
if v_hash.values() :
max_value = max(max(v_hash.values()), max_value)
else :
n_cnt = cur_cnt + 1
n = move_up(v_hash=v_hash)
q.append([n, n_cnt])
n = move_down(v_hash=v_hash)
q.append([n, n_cnt])
n = move_left(v_hash=v_hash)
q.append([n, n_cnt])
n = move_right(v_hash=v_hash)
q.append([n, n_cnt])
return max_value
print(main(graph))다른 사람 풀이
주목해야 할 부분은 아래와 같이 각 방향으로 진행하는 코드이다.
def up(board):
for c in range(n):
pointer = 0
for r in range(1, n):
if board[r][c]:
cur = board[r][c]
board[r][c] = 0
# 포인터가 가리키는 수가 0일 때
if board[pointer][c] == 0:
board[pointer][c] = cur
# 포인터가 가리키는 수와 현재 위치의 수가 같을 때
elif board[pointer][c] == cur:
board[pointer][c] *= 2
pointer += 1
# 포인터가 가리키는 수와 현재 위치의 수가 다를 때
else:
pointer += 1
board[pointer][c] = cur
return board이 코드를보면 pointer라는 변수를 활용해서 머지가 된지 안된지를 어떻게 회피할지와 정해주고 있다.
또한 0부터 시작하는게 아닌 1 또는 -2 부터 시작함으로써 불필요한 반복을 최소화하고 있다.
그리고 이건 나도 처음 보자마자 dfs로 풀 수 있겠다는 생각이 들었지만 구현 방법이 떠오르지 않았다.
또한 dfs를 선택하지 않은 이유 중 다른 하나는 baord가 매번 stack에 쌓이면 메모리 초과가 날 것이라고 생각했기 때문이다.
이번 기회를 통해서 dfs가 stack frame에 쌓여서 에러가 발생하는 경우는 method 호출이 깊어져서 dfs method가 매우 많이 호출되는 경우에 발생한다는 사실을 인자하고 갔으면 좋겠다.
전체 코드
import sys
from copy import deepcopy
input = sys.stdin.readline
# INPUT
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
answer = 0
# UP
def up(board):
for c in range(n):
pointer = 0
for r in range(1, n):
if board[r][c]:
cur = board[r][c]
board[r][c] = 0
# 포인터가 가리키는 수가 0일 때
if board[pointer][c] == 0:
board[pointer][c] = cur
# 포인터가 가리키는 수와 현재 위치의 수가 같을 때
elif board[pointer][c] == cur:
board[pointer][c] *= 2
pointer += 1
# 포인터가 가리키는 수와 현재 위치의 수가 다를 때
else:
pointer += 1
board[pointer][c] = cur
return board
# DOWN
def down(board):
for c in range(n):
pointer = n - 1
for r in range(n - 2, -1, -1):
if board[r][c]:
cur = board[r][c]
board[r][c] = 0
if board[pointer][c] == 0:
board[pointer][c] = cur
elif board[pointer][c] == cur:
board[pointer][c] *= 2
pointer -= 1
else:
pointer -= 1
board[pointer][c] = cur
return board
# LEFT
def left(board):
for r in range(n):
pointer = 0
for c in range(1, n):
if board[r][c]:
cur = board[r][c]
board[r][c] = 0
if board[r][pointer] == 0:
board[r][pointer] = cur
elif board[r][pointer] == cur:
board[r][pointer] *= 2
pointer += 1
else:
pointer += 1
board[r][pointer]= cur
return board
# RIGHT
def right(board):
for r in range(n):
pointer = n - 1
for c in range(n - 2, -1, -1):
if board[r][c]:
cur = board[r][c]
board[r][c] = 0
if board[r][pointer] == 0:
board[r][pointer] = cur
elif board[r][pointer] == cur:
board[r][pointer] *= 2
pointer -= 1
else:
pointer -= 1
board[r][pointer] = cur
return board
# DFS
def dfs(board, cnt):
if cnt == 5:
# 2차원 배열 요소 중 가장 큰 값 반환
return max(map(max, board))
# 상, 하, 좌, 우로 움직여 리턴한 값들 중 가장 큰 값 반환
# board를 꼭 deepcopy하여 함수를 거친 board값이 다음 함수에 들어가지 못하도록 해주어야 한다.
return max(dfs(up(deepcopy(board)), cnt + 1), dfs(down(deepcopy(board)), cnt + 1), dfs(left(deepcopy(board)), cnt + 1), dfs(right(deepcopy(board)), cnt + 1))
print(dfs(board, 0))