김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 12100 2048 (Easy) 파이썬(Python)

문제 링크

그냥 구현하면 되는 문제이지만, 구현이 Easy하지는 않은 문제.
구현을 크게 방향에 따라 슬라이딩시키는 함수, 슬라이딩된 방향으로 실제 각 블럭을 움직이는 함수, 움직인 블럭의 충돌 판정(합체)을 하는 함수로 나누었다.
처음에 2차원 배열을 얕은 복사를 해놓고 왜 틀리지 한참을 고민했다.

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

n = int(input())
boardOriginal = [list(map(int, input().split())) for _ in range(n)]
# 최대 5회의 이전 이동을 저장하는 리스트
boardSeries = [boardOriginal] + [[[0] * n for _ in range(n)] for _ in range(5)]

# 0상 1하 2좌 3우
def slide(direction, board):
    # 보드를 슬라이딩하는 함수
    # 충돌 판정을 저장하는 리스트
    # 이게 필요한 이유는 합체한 블럭이 또 합체해버리면 안 되기 때문이다
    isCollide = [[0] * n for _ in range(n)]
    
    # 방향에 따라 시작점이 다르다
    # 해당 방향부터 합체가 이루어져야 하기 때문
    if direction == 0:
        istart, iend, istep = 1, n, 1
        jstart, jend, jstep = 0, n, 1
    elif direction == 1:
        istart, iend, istep = n-2, -1, -1
        jstart, jend, jstep = 0, n, 1
    elif direction == 2:
        istart, iend, istep = 0, n, 1
        jstart, jend, jstep = 1, n, 1
    else:
        istart, iend, istep = 0, n, 1
        jstart, jend, jstep = n-2, -1, -1
    for i in range(istart, iend, istep):
        for j in range(jstart, jend, jstep):
            if not board[i][j]:
                continue
            move(i, j, direction, board, isCollide)

def move(i, j, direction, board, isCollide):
    # 각 블럭 하나하나를 움직이는 함수
    # temp는 이동해야 할 칸 수
    temp = 0
    if direction == 0:
        while i - temp > 0 and not board[i-temp-1][j]:
            temp += 1
        x, y = i - temp, j
    elif direction == 1:
        while i + temp < n - 1 and not board[i+temp+1][j]:
            temp += 1
        x, y = i + temp, j
    elif direction == 2:
        while j - temp > 0 and not board[i][j-temp-1]:
            temp += 1
        x, y = i, j - temp
    else:
        while j + temp < n - 1 and not board[i][j+temp+1]:
            temp += 1
        x, y = i, j + temp
    
    # 블럭 이동
    board[x][y] = board[i][j]
    
    # 만약 블럭이 위치를 벗어났다면 원래 자리의 블럭 삭제
    if x != i or y != j:
        board[i][j] = 0
    collide(x, y, direction, board, isCollide)

def collide(i, j, direction, board, isCollide):
    # 충돌 판정을 검사해 블럭의 합체 여부를 판단하는 함수
    if direction == 0:
        x, y = i - 1, j
    elif direction == 1:
        x, y = i + 1, j
    elif direction == 2:
        x, y = i, j - 1
    else:
        x, y = i, j + 1
    if 0 <= x < n and 0 <= y < n and board[i][j] == board[x][y] and not isCollide[x][y]:
        board[x][y], board[i][j] = 2 * board[x][y], 0
        isCollide[x][y] = 1

def dfs(t, direction):
    # 깊은 복사로 이전 시간대의 보드 복사
    boardSeries[t] = deepcopy(boardSeries[t-1])
    # 슬라이드 수행
    slide(direction, boardSeries[t])
    if t == 5:
        # t가 5면 5회 이동한 것이므로 최대값을 반환
        return max(map(max, boardSeries[t]))
    
    # ans는 반환값
    ans = 0
    for i in range(4):
        ans = max(ans, dfs(t+1, i))
    return ans

ans = 0
for i in range(4):
    ans = max(ans, dfs(1, i))

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑