99클럽 코테 스터디 37일차 TIL, 백준 / 2048 (Easy) / 12100

🔑 오늘의 학습 키워드 : 구현, dfs

🔗 문제링크 https://www.acmicpc.net/problem/12100

 

import sys
from copy import deepcopy

input = sys.stdin.readline

N = int(input())
board = []
for _ in range (N):
    board.append(list(map(int,input().split())))
           
def up(board):
    for j in range(N):
        pointer = 0
        for i in range(1, N):
            if board[i][j]:
                tmp = board[i][j]
                board[i][j] = 0
                if board[pointer][j] == 0:
                    board[pointer][j] = tmp
                elif board[pointer][j] == tmp:
                    board[pointer][j] *= 2
                    pointer += 1
                else :
                    pointer += 1
                    board[pointer][j] = tmp
    return board
def down(board):
    for j in range(N):
        pointer = N - 1
        for i in range(N - 2, -1, -1):
            if board[i][j]:
                tmp = board[i][j]
                board[i][j] = 0
                if board[pointer][j] == 0:
                    board[pointer][j] = tmp
                elif board[pointer][j]  == tmp:
                    board[pointer][j] *= 2
                    pointer -= 1
                else:
                    pointer -= 1
                    board[pointer][j] = tmp
    return board

def left(board):
    for i in range(N):
        pointer = 0
        for j in range(1,N):
            if board[i][j]:
                tmp = board[i][j]
                board[i][j] = 0
                if board[i][pointer] == 0:
                    board[i][pointer] = tmp
                elif board[i][pointer] == tmp:
                    board[i][pointer] *= 2
                    pointer += 1
                else :
                    pointer +=1
                    board[i][pointer] = tmp
    return board

def right(board):
    for i in range(N):
        pointer = N - 1
        for j in range(N - 2, -1, -1):
            if board[i][j]:
                tmp = board[i][j]
                board[i][j] = 0
                if board[i][pointer] == 0:
                    board[i][pointer] = tmp
                elif board[i][pointer]  == tmp:
                    board[i][pointer] *= 2
                    pointer -= 1
                else:
                    pointer -= 1
                    board[i][pointer] = tmp
    return board

def dfs(board, cnt):
    if cnt == 5:
        # 2차원 배열 요소 중 가장 큰 값 반환
        return max(map(max, board))
    return max(dfs(up(deepcopy(board)), cnt + 1), dfs(down(deepcopy(board)), cnt + 1), dfs(left(deepcopy(board)), cnt + 1), dfs(right(deepcopy(board)), cnt + 1))

print(dfs(board, 0))

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

구현문제네

 

각 방향에 맞는 함수를 구한 후 재귀를 돌려서 최대값 찾으면 되겠다

 

⏰ 예상 시간 복잡도 O(N ^ 2)

제한 사항

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)

😎 알고리즘 개요

1. 이 문제는 당기는 것을 잘 해야하고

2. 재귀로 구현을 잘 해야한다.

 

1. 당기기

[ 4, 0, 0, 2 ] 이렇게 생긴 블록이 있다고 생각을 해보면

왼쪽으로 밀면 [ 4, 2 , 0 ,0 ] 이렇게 된다.

 

이것은 투 포인터로 왼쪽 ( 0을 가리키고 있는 부분 인덱스로는 1) 과 오른쪽 (2를 가리키고 있는 부분 인덱스로는 3) 을 교환한 것이다.

 

이것을 기초로 구현을 했다

 

이벤트가 일어나는 시점은 탐색을 해나가면서 0이 아닌 값을 만날때이다 

 

그 경우 3가지로 나뉘는데

 

1. 왼쪽 포인터가 가리키고 있는 숫자가 0인 경우

pointer : 0

ex ) [ 4 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2 ] -> [ 4 , 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

 

2. 왼쪽 포인터가 가리키고 있는 숫자가 자기랑 같아서 합쳐지는 경우

pointer : 4

ex ) [ 4 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 ] -> [ 8 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

 

3. 왼쪽 포인터가 가리키고 있는 숫자가 0도 아니고 자기랑 같지도 않아서 그냥 당겨지는 경우가 있다.

pointer : 4

ex ) [ 4 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2 ] -> [ 4 , 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

 

이렇게 경우를 나눠서 처리를 해주는 함수를 방향별로 작성했다.

 

2. 재귀

현재 상황판에서 상, 하, 좌, 우로 움직여 리턴한 값들 중 가장 큰 값 반환하는 재귀 함수를 작성했다.

def dfs(board, cnt):
    if cnt == 5:
        # 2차원 배열 요소 중 가장 큰 값 반환
        return max(map(max, board))
    return max(dfs(up(deepcopy(board)), cnt + 1), dfs(down(deepcopy(board)), cnt + 1), dfs(left(deepcopy(board)), cnt + 1), dfs(right(deepcopy(board)), cnt + 1))

 

✅ 오늘의 회고

 

- 구현 어렵다 :(

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL