[백준, 파이썬] 12100번_2048(easy) - 골드 2 | 브루트 포스(brute force) 알고리즘

📌 백준 골드 2 : 2048(easy)

요즘 회사일이 바빠서 자기개발에 소홀해져 있었다.. 반성 중..!
이번주부터는 다시 힘내기~😤

5월 말에는 회사에서 진행하는 코딩테스트도 있다!
제일 어려운 레벨을 덜컥 신청했는데.. 열심히 해서 꼭 통과해볼 예정이다

📝 내 풀이

import sys
from copy import deepcopy

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

# 최대 움직임 횟수가 5회이므로 모든 경로 탐색
# 첫 시작 경우의 수는 상,하,좌,우 4가지
# [상,하,좌,우] = [0,1,2,3]

# (현재 경우의 수에서 board, 진행 방향)
def move(path,dir):
    # 상
    if dir == 0:
        for y in range(n):
            # 가장 높은 우선순위
            p = 0
            # 상 -> 하 탐색
            for x in range(1,n):
                if path[x][y] == 0:
                    continue
                now = path[p][y]
                next = path[x][y]
                path[x][y] = 0
                if now == 0:
                    path[p][y] = next
                elif now == next:
                    path[p][y] += next
                    p += 1
                # now가 0도 아니고 next와 같지도 않을 때, 미리 다음 now의 값을 갱신
                else:
                    p += 1
                    path[p][y] = next
    # 하
    elif dir == 1:
        for y in range(n):
            p = n-1
            # 하 -> 상 탐색
            for x in range(n-2,-1,-1):
                if path[x][y] == 0:
                    continue
                now = path[p][y]
                next = path[x][y]
                path[x][y] = 0
                if now == next:
                    path[p][y] += next
                    p -= 1
                elif now == 0:
                    path[p][y] = next
                else:
                    p -= 1
                    path[p][y] = next
    # 좌
    elif dir == 2:
        for x in range(n):
            p = 0
            # 우 -> 좌 탐색
            for y in range(1,n):
                # 0이면 건너뜀
                if path[x][y] == 0:
                    continue
                now = path[x][p]
                next = path[x][y]
                path[x][y] = 0
                if now == next:
                    path[x][p] += next
                    path[x][y] = 0
                    p += 1
                elif now == 0:
                    path[x][p] = next
                    path[x][y] = 0
                else:
                    p += 1
                    path[x][p] = next
    # 우
    else:
        for x in range(n):
            p = n-1
            # 좌 -> 우 탐색
            for y in range(n-2,-1,-1):
                # 0이면 건너뜀
                if path[x][y] == 0:
                    continue
                now = path[x][p]
                next = path[x][y]
                path[x][y] = 0
                if now == next:
                    path[x][p] += next
                    p -= 1
                elif now == 0:
                    path[x][p] = next
                else:
                    p -= 1
                    path[x][p] = next
    return path

def dfs(board2,cnt,answer):
    if cnt >= 5:
        maxv = 0
        for i in range(n):
            maxv = max(maxv,max(board2[i]))
        answer.append(maxv)
        return

    for i in range(4):
        # 깊은 복사
        next_board = move(deepcopy(board2),i)
        dfs(next_board,cnt+1,answer)
    return answer

answer = dfs(board,0,[])
print(max(answer))

🔮 풀이

브루트 포스를 사용해서 푼 문제다!
시간복잡도 측면에서 그리 효율성이 좋진 않은 알고리즘이지만,

본 문제는 5회 까지의 움직임만 허용되므로 사용해도 된다고 판단했다.

브루트 포스(Brute Force)

• 완전탐색 알고리즘이다. (Brute Force = 직역하면 무식한 힘..?)
• 모두 하나하나 비교하는 방법.
• 문자열을 모두 돌면서 순차적으로 비교하며 답을 도출한다.
• 100% 정답을 보장함. But 모든 자료를 탐색하므로 시간 효율성은 떨어짐

• 시간복잡도 : O(m*n) -> 가로x세로

🔅 14%에서 통과를 못할 때 해봐야할 TestCase

나는 14%에서 계속 막혀있어서 시간을 꽤 할애했는데, 아래 TestCase를 통해 코드에서 빠뜨린 부분을 구현하니까 바로 통과할 수 있었다.

input :
4
2 0 0 2
2 0 0 2
2 0 0 2
2 0 0 2

위 input을 위나 아래쪽으로 한 번 움직였을 때,

❗️위로 1번

answer :
4 0 0 4
4 0 0 4
0 0 0 0
0 0 0 0

틀렸을 때 출력 :
4 0 0 4
2 0 0 2
2 0 0 2
0 0 0 0