[백준/Python] 12100. 2048 (Easy) - 범용적 함수 및 구현팁

Choi Jimin·2023년 11월 3일

백준(BOJ)

목록 보기

18/28

본 포스팅에서는 좀 더 범용적인 함수 구현과 몇 가지 구현팁(배열 회전, n진법 활용)에 초점을 두고 있다.
좀 더 직관적인 풀이 방법은 아래 포스팅을 참고 바란다.

[백준/Python] 12100. 2048 (Easy)

📄 문제

백준
난이도 : Gold 2
문제 제목 : 2048 (Easy)

✏️ 풀이 1

import sys
from collections import deque
from copy import deepcopy

input = sys.stdin.readline
n = int(input())
board = []
for _ in range(n):
	board.append(list(map(int, input().split())))

def rotate(origin):
    tmp = []
    for i in range(n):
        tmp2 = []
        for j in range(n):
            tmp2.append(origin[i][j])
        tmp.append(tmp2)
    
    for i in range(n):
        for j in range(n):
            origin[i][j] = tmp[n - 1 - j][i]

def upd(dir, board):
	while dir > 1:
		rotate(board)
		dir -= 1
	for i in range(n):
		check_arr = [0] * n
		idx = 0
		for j in range(n):
			if not board[i][j]:
				continue
			if not check_arr[idx]:
				check_arr[idx] = board[i][j]
			elif check_arr[idx] == board[i][j]:
				check_arr[idx] *= 2
				idx += 1
			else:
				idx += 1
				check_arr[idx] = board[i][j]
		for j in range(n):
			board[i][j] = check_arr[j]
		
mx = 0
for i in range(4 ** 5):
    for _ in range(5):
        upd(i % 4, board)
        i //= 4
    
    for r in range(n):
        for c in range(n):
            mx = max(mx, board[r][c])

print(mx)

✅ 풀이 한줄 설명:
1. 게임보드를 상하좌우 중 한 쪽으로 민 결과를 업데이트하기 - 💫 배열 회전 이용하기
2. 5번 각각 미는 방향(조합)을 정하기 - 💫 4진법 이용하기

✅ 풀이 자세한 설명:
2번의 경우 백트래킹(DFS)으로 정할 수도 있지만 4진법을 이용해서 정할 수도 있다.
그리고 1번의 경우, 한 쪽으로 밀었을 때 나올 수 있는 모든 경우에 대해 잘 정리하여 구현해야 한다. 상하좌우 중 한 경우에 대한 게임보드 업데이트 함수만 구현한다면, 나머지 세 경우도 같은 과정을 거치기 때문에 쉽게 해결할 수 있다.

🍎 1. 게임보드를 상하좌우 중 한 쪽으로 민 결과를 업데이트하기
게임보드를 왼쪽으로 밀 때를 기준으로 함수를 만들어보자.
게임보드의 한 행이 있을 때를 생각해보면, for문을 돌려 왼쪽 칸부터 확인하여 숫자면 왼쪽으로 밀어 수를 합치거나, 왼쪽으로 밀기만 할 것이다. 그리고 빈 칸(0)이면 패스하여 다음 칸(오른쪽 칸)을 확인할 것이다.
즉, 경우를 정리해보면 다음과 같다.

현재 칸이 빈 칸(0)이면 패스하기
현재 칸이 숫자 칸이면
- 왼쪽으로 밀기
- 왼쪽 수와 같은 수이면 합치기

이렇게 세 경우가 있음에 주의하여 함수를 구현해보면 다음과 같이 2중 for문으로 구현 가능하다.

def upd():
	for i in range(n):
    	# board[i] 자체를 바로바로 업데이트하지 않고, 업데이트 완료된 값을 가질 새로운 리스트를 생성
		check_arr = [0] * n
        # 숫자를 당겨올 대상 위치 (혹은 합친 수를 놓을 위치)
		idx = 0
		for j in range(n):
        	# 현재 칸이 빈 칸이면 패스
			if not board[i][j]:
				continue
            # 현재 칸이 숫자이고 check_arr[idx]가 빈 칸이면 check_arr[idx]에 숫자 담기
			if not check_arr[idx]:
				check_arr[idx] = board[i][j]
            # 현재 칸 숫자와 check_arr[idx] 숫자가 같으면 합치고, idx 오른쪽으로 한 칸 옮기기
			elif check_arr[idx] == board[i][j]:
				check_arr[idx] *= 2
				idx += 1
            # 현재 칸 숫자와 check_arr[idx] 숫자가 다르면 idx 오른쪽으로 한 칸 옮기고, 옮긴 칸에 숫자 담기
			else:
				idx += 1
				check_arr[idx] = board[i][j]
        # 업데이트 완료된 check_arr를 board[i]로 옮기기
		for j in range(n):
			board[i][j] = check_arr[j]

아마 주석과 함께 읽어보면 이해가 될 것이다.
board[i] 를 바로바로 업데이트해도 되지만, 새로운 행 check_arr 를 생성해서 사용하면 덜 헷갈리고 깔끔하게 구현이 가능하다.

위와 같이 '왼쪽으로 밀기'를 구현한 upd()를 상하좌우 밀기 모두에 사용할 수 있다. 물론 비슷한 방법으로 상하좌우 밀기 각각의 함수 4개를 구현할 수도 있지만, board 를 90도 회전시킴으로써 위의 upd() 함수를 더 범용적으로 사용할 수도 있다.

배열을 오른쪽으로 90도 회전시키는 함수는 다음과 같이 구현 가능하다.

def rotate(board):
	tmp = []
	for i in range(r):
		tmp2 = []
		for j in range(c):
			tmp.append(board[i][j])
		tmp.append(tmp2)

	board = [[0] * r for _ in range(c)]
	for i in range(c):
		for j in range(r):
			board[i][j] = tmp[r - 1 - j][i]
	r, c = c, r
	return board, r, c

물론 이 문제에서 board 는 정사각형이기 때문에 중간에 있는 board = [[0] * r for _ in range(c)]는 굳이 수행하지 않아도 된다.
배열 회전에 대한 자세한 설명이 필요하다면 다음 포스팅을 참고 바란다.
📋 참고 포스팅: 배열 회전 함수 구현하기

결론적으로 상하좌우 모두에 범용적 사용이 가능하도록 upd() 함수를 수정하면 다음과 같다.

def upd(dir):
	# 'dir == 0'부터 왼쪽, 아래, 오른쪽, 위라고 하자.
    # (사실 0은 왼쪽, 1~3은 각기 다른 방향이라고만 생각하면 됨)
    # 왼쪽 밀기에 적합하도록 board를 필요한 만큼 회전시키자.
	while dir > 1:
		rotate()
		dir -= 1
	for i in range(n):
		check_arr = [0] * n
		idx = 0
		for j in range(n):
			if not board[i][j]:
				continue
			if not check_arr[idx]:
				check_arr[idx] = board[i][j]
			elif check_arr[idx] == board[i][j]:
				check_arr[idx] *= 2
				idx += 1
			else:
				idx += 1
				check_arr[idx] = board[i][j]
		for j in range(n):
			board[i][j] = check_arr[j]

🍎 2. 5번 각각 미는 방향(조합)을 정하기
미는 방향을 5번 정하는 것은 백트래킹(DFS)을 이용해도 되지만, 다음의 세 가지 조건이 충족되기 때문에 4진법을 사용해도 된다.

변수(각 방향 순서)들이 가질 수 있는 값이 여러개
모든 방향 조합을 확인하고 싶은 상황
변수(각 방향 순서)들끼리 독립적

예를 들어 n = 5 일 때, [상, 하, 하, 좌, 좌] 의 순서로 게임보드를 밀 수 있다. 이때 각 순서는 '변수'로 상하좌우 4가지 값을 가질 수 있으며, 각 순서는 서로 독립적이다. 그리고 모든 방향 순서 조합을 필요로 한다.

이 문제의 경우 방향이 총 4가지이니 4진법을 사용하면 된다.

잘 이해가 되지 않는다면 다음 포스팅의 '✅ 풀이 자세한 설명 > 🍎 1. 각 cctv의 방향 정하기'를 참고 바란다. 아래 포스팅에서 '카메라 개수'를 이 문제의 '보드를 미는 횟수'라고 생각하면 상황이 같다.
📋 참고 포스팅: [백준/Python] 15683. 감시 - 4진법 이용하기

4진법을 이용한 풀이는 다음과 같다.

mx = 0
# 방향은 4가지, 보드 미는 횟수는 각각 5번 -> 모든 방향 조합은 (4 ** 5 = 1024)개
for i in range(4 ** 5):
	# 한 방향 조합에 대해 (예: 00001, 00002, ... 33333)
    for _ in range(5):
    	# 각 자리 별로 바로 밀기(upd()) 수행
        upd(i % 4, board)
        i //= 4
    
    # 현재 방향 조합에 대한 5회 밀기 완료 후, mx 갱신
    for r in range(n):
        for c in range(n):
            mx = max(mx, board[r][c])

print(mx)