[Python][백준] 12100번 2048(Easy)

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

공부 날짜 : 2022.08.22
정답 참조 여부 : X

2048게임을 시뮬레이션하는 테스트로 문제 제목에서처럼 Easy했다. (알고리즘 공부 1달차인데 바로 풀수있었으니 쉬운문제다.)

문제를 들었을때 4가지 방향으로 움직일 수 있고 5번 움직였을때 최대값을 찾는 문제이므로 dfs문제로 해결하면 되겠다 싶었다.

움직이는 방향에 따라 move함수를 만들고 결과를 반환해서 dfs를 구현해 주었고 2차원 이상의 배열이므로 deepcopy를 활용해서 결과데이터를 다음 노드로 보낼때 데이터를 보존하여 연산하였다.

시뮬레이션의 경우
결과를 저장할 2차원 배열을 만들어주고 입력받은 데이터의 방향에맞춰서 값을 체크한 뒤 결과를 저장하는 temp_data의 0에서부터 순차적으로 저장하고 값이 같을때 값을 2배로 만들어 주는 방식으로 구성했으며
이미 합쳐진 숫자의경우 값이 같더라도 다음자리에 값이 저장되어야 함으로 bool계수를 통해 이전에 값이 합쳐졌는지 여부를 판단하였다.

소스코드에서는 4가지 방향에따라 시뮬레이션 되는 상황을 각각 코드를 짜놓았지만 문제에서 최대값만 찾으면 되는 상황이기 때문에 한 방향으로만 시뮬레이션 되는 상황을 넣어두고 데이터의 행렬을 회전시키는 함수를 추가하여 만들면 코드가 더 깔끔하지 않았을까 생각된다.(물론 연산이 더 많아져서 시간초과가 될수도 있지만 다른방법도 생각이 나서 적어보았다)

소스코드

import sys
input = sys.stdin.readline
import copy

n = int(input())

data = []
for _ in range(n):
    data.append(list(map(int, input().split())))

#특정 방향으로 정렬하는 함수    
def move(data, v):

    temp_data = [[0]*n for _ in range(n)]
    
    #왼쪽 정렬
    if v == 0:                
        for i in range(n):
            #새로 만드는 행렬의 위치 방향에따라 행or축으로 쓰임 
            #첫번째 값을 0에넣기위해 초기값 -1
            size_ = -1        
            #합쳐졌는지 체크하는 bool
            check = False     
            for j in range(n):
                #0은 비어있음을 의미 비어있지 않고 값이 다르면 값을 대입
                if data[i][j] != 0 and temp_data[i][size_] != data[i][j]:    
                    size_ += 1
                    temp_data[i][size_] = data[i][j]
                    check = False
                #비어있고, 값이 같으면 2를 곱해줌
                #곱한뒤에 같은 경우는 그냥 값을 대입
                #ex)4488은 4와 4가 합쳐져서 8이되고 세번째 8이 합쳐진 8과 비교해서 같아짐
                elif data[i][j] != 0 and temp_data[i][size_] == data[i][j]:
                    if check:
                        size_ += 1
                        temp_data[i][size_] = data[i][j]
                        check = False
                    else:
                        temp_data[i][size_] *= 2
                        check = True

    #위쪽 정렬
    elif v == 1:                
        for j in range(n):
            size_ = -1          
            check = False       
            for i in range(n):
                if data[i][j] != 0 and temp_data[size_][j] != data[i][j]:    
                    size_ += 1
                    temp_data[size_][j] = data[i][j]
                    check = False
                elif data[i][j] != 0 and temp_data[size_][j] == data[i][j]:  
                    if check:
                        size_ += 1
                        temp_data[size_][j] = data[i][j]
                        check = False
                    else:
                        temp_data[size_][j] *= 2
                        check = True
    
    #오른쪽 정렬
    elif v == 2:                
        for i in range(n):
            size_ = 0
            check = False
            #방향을 신경써서 range설정
            for j in range(n-1,-1,-1):
                if data[i][j] != 0 and temp_data[i][size_] != data[i][j]:
                    size_ -= 1
                    temp_data[i][size_] = data[i][j]
                    check = False
                elif data[i][j] != 0 and temp_data[i][size_] == data[i][j]:
                    if check:
                        size_ -= 1
                        temp_data[i][size_] = data[i][j]
                        check = False
                    else:
                        temp_data[i][size_] *= 2
                        check = True
                        
    #아래쪽 정렬
    elif v == 3:                
        for j in range(n):
            size_ = 0
            check = False
            for i in range(n-1,-1,-1):
                if data[i][j] != 0 and temp_data[size_][j] != data[i][j]:
                    size_ -= 1
                    temp_data[size_][j] = data[i][j]
                    check = False
                elif data[i][j] != 0 and temp_data[size_][j] == data[i][j]:
                    if check:
                        size_ -= 1
                        temp_data[size_][j] = data[i][j]    
                        check = False
                    else:
                        temp_data[size_][j] *= 2
                        check = True


    return temp_data


result = 0

def dfs(board, count):
    global result
    if count == 5:
        for i in range(n):
            for j in range(n):
                result = max(result, board[i][j])
        return

    for i in range(4):
        tmp_board = move(copy.deepcopy(board), i)
        dfs(tmp_board, count + 1)
        

    
dfs(data, 0)
    
print(result)