문제 개요
2048 게임의 초기 보드(board)와 스와이프 방향을 나타내는 문자열(direction)이 주어졌을 때, 해당 방향으로 한 번 슬라이드한 이후의 다음 보드 상태를 구하는 프로그램을 작성해야 합니다.
2048 게임은 숫자가 채워진 4 x 4 크기의 보드에서 진행됩니다. 일부 칸은 비어 있으며, 여기서는 0으로 표현합니다. 플레이어는 "U"(위), "D"(아래), "L"(왼쪽), "R"(오른쪽) 네 방향 중 하나로 보드를 밀 수 있습니다. 슬라이드하면 모든 숫자가 해당 방향으로 최대한 이동하고, 인접해 있는 같은 숫자끼리는 정확히 한 번만 합쳐집니다.
예를 들어 다음과 같은 보드가 있고,
direction = "L"이라면 출력 결과는 아래와 같습니다.
해결 접근 방법
이 문제는 모든 방향의 처리를 왼쪽 슬라이드 하나로 통일하는 것이 핵심입니다. 보드를 반시계 방향으로 회전시키면 원하는 방향의 슬라이드가 항상 "왼쪽으로 밀기"로 변환되므로, 로직을 크게 단순화할 수 있습니다. 전체 과정은 다음과 같습니다.
direction이 "R"이라면 → 보드를 반시계 방향으로 두 번 회전
direction이 "U"라면 → 보드를 반시계 방향으로 한 번 회전
direction이 "D"라면 → 보드를 반시계 방향으로 세 번 회전
각 행 i(0부터 3까지)에 대해 다음을 수행합니다.
행에서 0이 아닌 원소들만 모아 새로운 리스트(row)를 만듭니다.
j를 0부터 2까지 순회하면서, j + 1이 리스트 길이보다 작고 row[j]와 row[j + 1]이 같다면:
row[j]를 두 배로 만들고
row[j + 1]을 삭제합니다.
row의 길이가 4보다 작아질 때까지 끝에 0을 채워 넣습니다.
board[i]에 row를 대입합니다.
마지막으로 보드를 원래 방향으로 되돌립니다.
direction이 "R"이라면 → 반시계 방향으로 두 번 회전
direction이 "U"라면 → 반시계 방향으로 세 번 회전
direction이 "D"라면 → 반시계 방향으로 한 번 회전
board를 반환합니다.
구현 예제
class Solution: def solve(self, board, direction): if direction == "R": board = rot_anti_clock_dir(rot_anti_clock_dir(board)) elif direction == "U": board = rot_anti_clock_dir(board) elif direction == "D": board = rot_anti_clock_dir(rot_anti_clock_dir(rot_anti_clock_dir(board))) for i in range(4): row = [x for x in board[i] if x] for j in range(3): if j + 1 < len(row) and row[j] == row[j + 1]: row[j] *= 2 del row[j + 1] while len(row) < 4: row += [0] board[i] = row if direction == "R": board = rot_anti_clock_dir(rot_anti_clock_dir(board)) elif direction == "U": board = rot_anti_clock_dir(rot_anti_clock_dir(rot_anti_clock_dir(board))) elif direction == "D": board = rot_anti_clock_dir(board) return board def rot_anti_clock_dir(x): x = [[x[i][j] for i in range(4)] for j in range(4)] return x[::-1] ob = Solution() matrix = [ [2, 0, 0, 2], [2, 2, 2, 2], [0, 4, 2, 2], [2, 2, 2, 0]] print(ob.solve(matrix, "L"))
동작 원리 살펴보기
rot_anti_clock_dir 함수는 먼저 행과 열을 뒤바꾸는 전치(transpose) 연산을 수행한 뒤, 각 행의 순서를 역순으로 뒤집습니다. 이 두 연산을 조합하면 보드가 반시계 방향으로 90도 회전한 것과 동일한 효과를 얻을 수 있습니다.
슬라이드 처리 부분에서는 각 행에서 0을 제거해 숫자들을 왼쪽으로 몰아 넣은 후, 왼쪽부터 차례대로 인접한 같은 숫자를 검사하여 합칩니다. 합치기가 끝나면 남은 자리를 0으로 채워 4칸 길이를 유지합니다. 이 과정에서 같은 숫자가 한 번 합쳐진 타일은 같은 슬라이드 내에서 다시 합쳐지지 않는다는 2048 게임의 규칙이 자연스럽게 지켜집니다.
입력
matrix = [ [2, 0, 0, 2], [2, 2, 2, 2], [0, 4, 2, 2], [2, 2, 2, 0]]
출력
[ [4, 0, 0, 0], [4, 4, 0, 0], [4, 4, 0, 0], [4, 2, 0, 0]]
정리
이 알고리즘은 시간 복잡도 O(N²)로 4 x 4 보드를 매우 빠르게 처리할 수 있습니다. 회전을 활용해 네 방향의 슬라이드를 하나의 왼쪽 슬라이드 로직으로 통합하는 기법은 2048 게임 AI를 만들거나 게임 로직을 구현할 때 널리 사용되는 패턴이므로, 잘 익혀두면 다양한 문제에 응용할 수 있습니다.