백준 12100 2048 파이썬 반례 O

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

12100번: 2048 (Easy)

*반례는 맨 아래 있다.*(정답이 아닌 움직였을때 어떻게 되야하는지.)

학창시절에 폰으로 즐겨 했던 게임을 구현해보는 문제였다.

 

문제에서 "최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오."라느 말을 처음 봤을때

모든 경우의 수를 돌려보면 될거 같았다. 그래서 0,1,2,3(오른쪽,왼쪽,아래,위)를 임의로 설정해 백트레킹을 해줘 길이가 5인 배열이 완성되면 저장해주는 형식으로 코드를 구성했다.

 

그리고 방향에 맞게 움직여주는  move 함수를 만들어서 모든 경우의 움직임을 해보고 그 중 최댓값을 출력하도록 프로그래밍했다. 오른쪽 이동만 구현해주고 나머지 방향은 zip(*list)와 reverse()를 적절히 사용해 편하게 구현해줬다.

 

 

import sys
import copy
input=sys.stdin.readline
def back(t):#백트레킹 부분 모든 경우의 수를 기록해줌.
    global re#모든 경우의 수가 담길 배열
    if len(t)==5:#길이가 최대 5이니 길이가 5면 저장해줌
        re.append(t.copy())
        return
    for i in range(4):
        t.append(i)
        back(t)
        t.pop()
        
def move(s,d):#움직이는 부분
    if d==0:#오른쪽)
        for i in range(n):
            t = []#우선 0이 아닌 숫자를 저장해줌
            for j in range(n):
                if s[i][j]!=0:
                    t.append(s[i][j])#저장!
            for j in range(len(t)-1,0,-1):#오른쪽으로 합쳐지니 오른쪽부터 합쳐줌
                if t[j-1]==t[j]:
                    t[j]= 2*t[j]
                    t[j-1]=0
            lt=[]#다시 합친 배열에서 0이 아닌 숫자를 저장해줌
            for j in range(len(t)):
                if t[j]!=0:
                    lt.append(t[j])#저장!
            
            s[i] = (n-len(lt))*[0]+lt#오른쪽으로 쭉 밀고 남은 왼쪽은 0으로 채워줌
    
    elif d==1:#왼쪽) 위에 코드를 최대한 활용해주기 위해서 배열을 뒤집어 줬다.
        for i in range(n):
            t = []
            for j in range(n):
                if s[i][j]!=0:
                    t.append(s[i][j])
            t.reverse()#배열을 뒤집어줌으로써 왼쪽부터 합치는 것과 같게 됨
            for j in range(len(t)-1,0,-1):
                if t[j-1]==t[j]:
                    t[j]= 2*t[j]
                    t[j-1]=0
            lt=[]
            for j in range(len(t)):
                if t[j]!=0:
                    lt.append(t[j])
            
            lt.reverse()#다시 돌려줘서 왼쪽이 앞에 오게 해줌
            s[i] = lt+(n-len(lt))*[0]#왼쪽으로 밀었으니 오른쪽에 빈곳은 0으로 채워줌.
            
    elif d==2:#아래) 이것 또한 위에 코드를 최대한 이용하기위해 zip(*list)를 통해 x,y,축 반전을 시켜줬다.
        s = list(zip(*s))
        for i in range(n):
            t = []
            for j in range(n):
                if s[i][j]!=0:
                    t.append(s[i][j])
            for j in range(len(t)-1,0,-1):
                if t[j-1]==t[j]:
                    t[j]= 2*t[j]
                    t[j-1]=0
            lt=[]
            for j in range(len(t)):
                if t[j]!=0:
                    lt.append(t[j])
            
            s[i] = (n-len(lt))*[0]+lt
        s = list(zip(*s))
        
    elif d==3:#위) 이것또한 마찬가지이다. 
        s = list(zip(*s))
        for i in range(n):
            t = []
            for j in range(n):
                if s[i][j]!=0:
                    t.append(s[i][j])
            t.reverse()
            for j in range(len(t)-1,0,-1):
                if t[j-1]==t[j]:
                    t[j]= 2*t[j]
                    t[j-1]=0
            lt=[]
            for j in range(len(t)):
                if t[j]!=0:
                    lt.append(t[j])
            
            lt.reverse()
            s[i] = lt+(n-len(lt))*[0]
        s = list(zip(*s))
    return s

re =[]
back([])
n = int(input())
s = [list(map(int,input().split())) for _ in range(n)]
maxs=-1#최댓값을 저장해줄 변수
for i in re:#처음에 구한 모든 경우의 수를 돌려준다.
    se = copy.deepcopy(s)#2차원 배열을 deepcopy를 사용해 복사해서 사용한다. 2차원 배열이므로 deepcopy사용해야함
    for k in i:
        se = move(se,k)#방향에 맞게 움직여준다.
    for i in range(n):
        maxs = max(maxs,max(se[i]))#모든 움직임이 끝나고 i경우에서 최댓값을 찾는 과정이다. 
print(maxs)#결과적으로 모든 결과에서 나올 수 있는 숫자중 최댓값이 저장되어있다.

밑에는 반례이다.

3 #오른쪽

2 0 2

4 4 4

8 8 8

결과 #이런 경우 때문에 t배열에 0이 아닌 수를 저장해준 것이였다.

0 0 4

0 4 8

0 8 16

 

4 #오른쪽
2 4 2 2
0 0 0 0
0 0 0 0
0 0 0 0

결과

0 2 4 4
0 0 0 0
0 0 0 0
0 0 0 0

#이런 경우 때문에 t배열을 합쳐준뒤 합쳐진 숫자를 0으로 해주고  다시 lt 배열을 만들어 0이 아닌 수를 저장해준것이다. (처음에는 t[j-1]=0이 아니라 t.pop(j-1)를 해줘서 한번 움직였을때 여러번 합쳐졌던 것이다.)

for j in range(len(t)-1,0,-1):#수정전 코드
                if t[j-1]==t[j]:
                    t[j]= 2*t[j]
                    t.pop(j-1)
            s[i] = (n-len(t))*[0]+t
            
            
for j in range(len(t)-1,0,-1):#수정된 코드
                if t[j-1]==t[j]:
                    t[j]= 2*t[j]
                    t[j-1]=0
            lt=[]
            for j in range(len(t)):
                if t[j]!=0:
                    lt.append(t[j])
            s[i] = (n-len(lt))*[0]+lt