[백준 알고리즘/Python] 백준 112100번 2048 (Easy), 파이썬 설명

1. 문제 출처

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

2. 생각 정리

 - 오른쪽, 왼쪽, 위쪽, 아래쪽 이동을 전부 다 구현하기는 너무 복잡함.

 - 따라서, 행렬을 회전시켜서 하나의 이동(왼쪽)으로만 구현할 것임.

 - 최대 5번 이동은 중복 순열을 사용하면 될 듯 함.

 

3. 조각 코드

- 행렬을 시계, 반시계 방향으로 회전하는 코드. 기억해두면 유용하게 쓰일 때가 많음

# 행렬 시계방향 90도 회전
def rotate_90():
    global lst
    lst = list(map(list, zip(*lst[::-1])))
    
# 행렬 반시계방향 90도 회전
def rotate_reverse():
    global lst
    lst = list(map(list, zip(*lst)))[::-1]

 

- 숫자들 왼쪽으로 합치는 함수

# 왼쪽으로 합치는 명령
def left():
    global lst
    # 0이 중간에 있는 경우 방지하기위해 0을 제일 끝으로 옮기기
    for i in range(n):
        if 0 in lst[i]:
            cnt = 0
            while 0 in lst[i]:
                lst[i].remove(0)
                cnt += 1
            for u in range(cnt):
                lst[i].append(0)
                
        #이미 합친 부분은 또 합쳐지면 안되니까 체크하는 리스트 선언
        chk = [False for _ in range(n)]
        
        # 숫자가 같은 경우 합치고 뒤에 합쳐진 인덱스 값은 0으로 초기화.
        for j in range(0,n-1):
            k = j + 1
            if lst[i][j] == lst[i][k] and chk[j] is False and chk[k] is False:
                lst[i][j] += lst[i][k]
                lst[i][k] = 0
                chk[j] = True
                chk[k] = True
        # 다시 0이 중간에 있기때문에 0을 제일 끝으로 옮기기
        if 0 in lst[i]:
            cnt = 0
            while 0 in lst[i]:
                lst[i].remove(0)
                cnt += 1
            for u in range(cnt):
                lst[i].append(0)
    return

 

- 오른쪽, 위쪽, 아래쪽 명령어 함수

# 시계방향 90도를 돌려서 왼쪽으로 명령을 하면 아래쪽 명령이랑 같음.
def down():
	# 90도 회전
    rotate_90()
    # 왼쪽 명령
    left()
    # 반시계 90도 회전
    rotate_reverse()
    return

# 시계방향 180도 돌려서 왼쪽 명령 == 오른쪽 명령
def right():
    rotate_90()
    rotate_90()
    left()
    rotate_reverse()
    rotate_reverse()
    return

# 시계방향 270도 돌려서 왼쪽명령 == 위쪽 명령
# 지금 생각해보니까 반대로 90도 한번 돌리는게 더 효율적일 듯 함.
def up():
    rotate_90()
    rotate_90()
    rotate_90()
    left()
    rotate_reverse()
    rotate_reverse()
    rotate_reverse()
    return

 

- 최대 5번 명령 경우의 수 찾기 (중복 순열 이용)

# 0,1,2,3은 각각 왼쪽, 위쪽, 아래쪽, 오른쪽 명령
cmd = [0,1,2,3]

# 0,1,2,3 중에서 중복으로 순서 상관있는 5번 뽑기
cmds = list(product(cmd,repeat=5))
# cmds = [[0,0,0,0,0], [0,0,0,0,1]...

# 리스트 깊은 복사 
copys = [item[:] for item in lst]

# 순회하면서 최대값 찾기
for cmd in cmds:
    lst = [item[:] for item in copys]
    for a in cmd:
        if a == 0:
            left()
        elif a == 1:
            up()
        elif a == 2:
            down()
        elif a == 3:
            right()
    result.append(max(map(max,lst)))

 

 

4. 전체 코드

from itertools import product

n = int(input())
lst = []
for i in range(n):

    lst.append(list(map(int, input().split())))

def rotate_90():
    global lst
    lst = list(map(list, zip(*lst[::-1])))

def rotate_reverse():
    global lst
    lst = list(map(list, zip(*lst)))[::-1]


def left():
    global lst
    for i in range(n):
        if 0 in lst[i]:
            cnt = 0
            while 0 in lst[i]:
                lst[i].remove(0)
                cnt += 1
            for u in range(cnt):
                lst[i].append(0)
        chk = [False for _ in range(n)]
        for j in range(0,n-1):
            k = j + 1
            if lst[i][j] == lst[i][k] and chk[j] is False and chk[k] is False:
                lst[i][j] += lst[i][k]
                lst[i][k] = 0
                chk[j] = True
                chk[k] = True
        if 0 in lst[i]:
            cnt = 0
            while 0 in lst[i]:
                lst[i].remove(0)
                cnt += 1
            for u in range(cnt):
                lst[i].append(0)
    return

def right():
    rotate_90()
    rotate_90()
    left()
    rotate_reverse()
    rotate_reverse()
    return

def up():
    rotate_90()
    rotate_90()
    rotate_90()
    left()
    rotate_reverse()
    rotate_reverse()
    rotate_reverse()
    return

def down():
    rotate_90()
    left()
    rotate_reverse()
    return



result = []
cmd = [0,1,2,3]
cmds = list(product(cmd,repeat=5))

copys = [item[:] for item in lst]
for cmd in cmds:
    lst = [item[:] for item in copys]
    for a in cmd:
        if a == 0:
            left()
        elif a == 1:
            up()
        elif a == 2:
            down()
        elif a == 3:
            right()
    result.append(max(map(max,lst)))

print(max(result))

 

5. 마무리

- 생각보다 쉽지만은 않았던 문제.

- 이런 류의 구현 문제가 나올때 행렬 회전이 굉장히 도움 될 듯 함.(커맨드 하나로 4개 똑같은 효과)

- 최대 5번 찾을때 dfs써도 될 거 같은데, 나중에 풀땐 dfs로 풀어보려고 함.