[백준] 12100 - 2048 (Easy) [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀

문제 👉 12100번: 2048 (Easy)

1. 문제

1. N*N 크기의 보드에서 전체 블록을 상하좌우 네 방향 중 하나로 이동시킨다.
2. 이동할 때, 같은 값을 가진 두 블록이 충돌하면 두 블록을 하나로 합치고 값을 2배로 바꾼다.
3. 이미 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다.
4. 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 출력한다.

2. 풀이

시뮬레이션 과 DFS를 이용한 문제 풀이

1. 보드가 상,하,좌,우로 움직이는 함수 구현
2. 현재 보드에서 최대값을 찾는 함수 구현
3. DFS 함수 구현

3. 코드

import copy
N = int(input())
B = [list(map(int, input().split())) for _ in range(N)]
dx, dy = [-1,1,0,0] ,[0,0,-1,1]
ret = -1

def solution():

    def move_left(board):
        for i in range(N):                      
            p_idx = 0
            p_val = 0
            for j in range(N):                          
                if board[i][j] == 0:                # 현재값이 0이면
                    continue                            # 건너뛴다
                if p_val == 0:                      # prev_val 0이면
                    p_val = board[i][j]                 # p_val 현재값 할당
                else:
                    if p_val == board[i][j]:        # 이전값과 현재값 같다면
                        board[i][p_idx] = 2*p_val       # 이전값 2배
                        p_val = 0                       # prev_val 0으로 초기화
                    else:                           # 이전값과 현재값 다르면
                        board[i][p_idx] = p_val         # 이전값에 p_val 할당
                        p_val = board[i][j]             # p_val 현재값 할당
                    p_idx += 1                      # p_idx 오른쪽으로 이동
                board[i][j] = 0                     # 현재값 0으로 초기화
            if p_val != 0:                      # p_val 0이 아니라면
                board[i][p_idx] = p_val             # 이전값에 p_val 할당
        return board

    def move_right(board):
        for i in range(N):
            p_idx = N-1
            p_val = 0
            for q in range(N-1, -1, -1):
                if board[i][q] == 0:                    
                    continue 
                if p_val == 0:                          
                    p_val = board[i][q]                
                else:                                   
                    if p_val == board[i][q]:            
                        board[i][p_idx] = 2*p_val       
                        p_val = 0                       
                    else:                               
                        board[i][p_idx] = p_val  
                        p_val = board[i][q]            
                    p_idx -= 1                                             
                board[i][q] = 0                         
            if p_val != 0: 
                board[i][p_idx] = p_val                 
        return board

    def move_up(board):
        for i in range(N):
            p_idx = 0
            p_val = 0
            for j in range(N):
                if board[j][i] == 0:
                    continue
                if p_val == 0:
                    p_val = board[j][i]
                else:
                    if p_val == board[j][i]:
                        board[p_idx][i] = 2*p_val
                        p_val = 0
                    else:
                        board[p_idx][i] = p_val
                        p_val = board[j][i]
                    p_idx += 1
                board[j][i] = 0
            if p_val != 0:
                board[p_idx][i] = p_val
        return board

    def move_down(board):
        for i in range(N):
            p_idx = N-1
            p_val = 0
            for j in range(N-1, -1, -1):
                if board[j][i] == 0:                    
                    continue 
                if p_val == 0:                          
                    p_val = board[j][i]                
                else:                                   
                    if p_val == board[j][i]:            
                        board[p_idx][i] = 2*p_val       
                        p_val = 0                       
                    else:                               
                        board[p_idx][i] = p_val                      
                        p_val = board[j][i]
                    p_idx -= 1                      
                board[j][i] = 0     
            if p_val != 0: 
                board[p_idx][i] = p_val                 
        return board

    def find_max(arr):
        global ret
        for i in range(N):
            ret = max(ret, max(arr[i]))

    def dfs(arr, cnt):
        if cnt == 5:
            find_max(arr)
            return

        dfs(move_up(copy.deepcopy(arr)), cnt+1)
        dfs(move_down(copy.deepcopy(arr)), cnt+1)
        dfs(move_right(copy.deepcopy(arr)), cnt+1)
        dfs(move_left(copy.deepcopy(arr)), cnt+1)


    dfs(B, 0)
    return ret

print(solution())

• 결과는 480 ms 나왔다.
• 보드를 상,하,좌,우 4방향 움직이는 함수를 따로 구현해서 시간이 상당히 오래 걸렸다....
  나중에 시간되면 다시한번 작성해봐야겠다....

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋