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

문제 : 

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

12100번: 2048 (Easy)

 

1. 문제 이해하기

• 1 <= 크기 <= 20의 원소들은 0 또는 2의 제곱수(최대 1024)로 이루어진 보드가 주어집니다.
• 한 번의 이동(상, 하, 좌, 우)으로 전체의 블록이 이동할 수 있는데, 두 블록의 수가 같으면 (해당 값* 2)로 합치고 0이면 이동만 합니다. 
• 그리고 합쳐진 위치에서 연속으로 합쳐질 수 없고, 한 블록을 넘어서 합쳐질 수도 없습니다.
• 최대 5번 이동해서 만들 수 있는 보드 위에 있는 가장 큰 블록의 값을 출력
• 주어진 블록 이외에 추가되는 블록은 없습니다.

 

2.  문제 풀이 생각하기

1. 처음에는 한 방향씩 진행하면서 보드를 갱신하는 방식으로 생각을 했는데, 진행할 때마다 보드를 갱신해야 하는데, 그 부분이 쉽지 않아 모든 경우의 수를 만들어놓고 그 안에서 진행해야겠다고 생각했습니다.
2. 5번을 모두 수행해야 가장 큰 값이 나올 수 있으므로, 총 4개의 방향에서 중복을 허용해서 5번 뽑는 방법(중복순열) -> 4^5 = 1024가지가 나옵니다. 최대 20 x 20 크기에서 모든 보드를 5번 움직이는 과정을 1024 가지 해도 20 * 20 * 5 * 1024 = 2,048,000
3. 파이썬 itertools 모듈 안에 있는 product함수를 이용해서 모든 경우의 수를 구합니다.
4. 모든 경우의 수를 돌면서 그때마다 보드지를 복사하고, 5개의 방향을 담은 개별 경우의 수에서 먼저 각 블록이 병합됐는지를 확인하는 변수를 만듭니다.
5. 각 방향마다 해당 방향을 진행했을 때 가장 가장자리와 가까운 지점에서부터 가장자리 쪽의 수들과 비교해 나가면서 0이 나오면 스왑, 같은 수이면 병합 체크 후, 값을 갱신
6. 4 ~ 5 반복
7. 여기서 주의할 점은 중간에 0이 여러 개 나올 수 있으므로 0과 자리를 스왑 할 때는 continue를 하고, 병합할 때는 한 블록을 넘어서 병합을 또 하면 안 되므로 병합 코드는 끝에는 break로 끝내 주어야 합니다.

 

해당 예시에서 왼쪽으로 한 번 처리할 때의 과정입니다.

 

여기서 주의할 코드는 한 블록을 거쳐서 병합되지 않도록 0이 아니거나 같지 않으면 break 해야 합니다.

 

3. 차근차근 구현하기

# # 방향 -> 0 : 북, 1 : 남, 2 : 서, 3 : 동
from itertools import product
import sys, copy
input = sys.stdin.readline
n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
totalCase = list(product(range(4), range(4), range(4), range(4), range(4))) # 중복순열
maxValue = 0 # 답

for case in totalCase:
    gCopy = copy.deepcopy(g) # 보드지 복사
    for d in case:
        isMerged = [[0 for _ in range(n)] for _ in range(n)] # 해당 블록이 병합이 됐는지 안 됐는지 확인하는 배열
        # 북
        if d == 0:
            for j in range(n):
                for i in range(1, n):
                    for k in range(i - 1, -1, -1):
                        # 이미 병합한 경우
                        if isMerged[k][j]:
                            break
                        # 0을 만났을 때
                        if gCopy[k][j] == 0:
                            gCopy[k][j] = gCopy[k + 1][j]
                            gCopy[k + 1][j] = 0
                            continue
                        # 병합할 수 있는 경우
                        if gCopy[k][j] == gCopy[k + 1][j]:
                            isMerged[k][j] = 1
                            gCopy[k][j] = gCopy[k + 1][j] * 2
                            gCopy[k + 1][j] = 0
                            break
                        # 그 이외의 경우
                        else:
                            break
        # 남
        if d == 1:
            for j in range(n):
                for i in range(n - 2, -1, -1):
                    for k in range(i + 1, n):
                        if isMerged[k][j]:
                            break
                        if gCopy[k][j] == 0:
                            gCopy[k][j] = gCopy[k - 1][j]
                            gCopy[k - 1][j] = 0
                            continue
                        if gCopy[k][j] == gCopy[k - 1][j]:
                            isMerged[k][j] = 1
                            gCopy[k][j] = gCopy[k - 1][j] * 2
                            gCopy[k - 1][j] = 0
                            break
                        else:
                            break
        # 서                    
        if d == 2:
            for i in range(n):
                for j in range(1, n):
                    for k in range(j - 1, -1, -1):
                        if isMerged[i][k]:
                            break
                        if gCopy[i][k] == 0:
                            gCopy[i][k] = gCopy[i][k + 1]
                            gCopy[i][k + 1] = 0
                            continue
                        if gCopy[i][k] == gCopy[i][k + 1]:
                            isMerged[i][k] = 1
                            gCopy[i][k] = gCopy[i][k + 1] * 2
                            gCopy[i][k + 1] = 0
                            break
                        else:
                            break
        # 동                    
        if d == 3:
            for i in range(n):
                for j in range(n - 2, -1, -1):
                    for k in range(j + 1, n):
                        if isMerged[i][k]:
                            break
                        if gCopy[i][k] == 0:
                            gCopy[i][k] = gCopy[i][k - 1]
                            gCopy[i][k - 1] = 0
                            continue
                        if gCopy[i][k] == gCopy[i][k - 1]:
                            isMerged[i][k] = 1
                            gCopy[i][k] = gCopy[i][k - 1] * 2
                            gCopy[i][k - 1] = 0
                            break
                        else:
                            break
    # 해당 케이스에서의 최대값 구하기
    for i in range(n):
        for j in range(n):
            if maxValue < gCopy[i][j]:
                maxValue = gCopy[i][j]
print(maxValue)

 

4. 피드백

• 예외 테스트 케이스를 몰라서 고생했었는데, 질문 검색에 있는 테스트 케이스를 참고했습니다. 시뮬레이션 문제를 풀 때 더 예외사항을 더 많이 생각할 수 있도록 훈련해야겠다고 생각했습니다.