[Python/BOJ] 백준 12100 2048(EASY)_확인방향을 어떻게 해야할지 _[DFS,백트래킹,구현]

 

 

복습 :

🎉 20220911 

🐾 20220916

 

백트래킹 문제인데 숫자들을 상하좌우 각각 구분해서 다르게 합쳐주는 코드를 만드는 것이 쉽지않았다. 

 

 

 

 

밑 그림과 같이 블록을 확인하면된다. 

그 이유는 곰곰히 생각하면 알 수 있다.

상은 위로 블록들을 올리는데 

동일한 값의 블록을 찾아야하고 이동하려는 쪽의 칸이 먼저 합쳐지기때문에 위에서 아래로 탐색한다. 

 

 

좌를 설명해보면

왼쪽으로 블록을 옮기므로 블록이 합해지는 것이 왼쪽에서 오른쪽으로 탐색해야한다. 

 

 

 

 

 

코드 : 

 

from collections import deque
import copy

def get(i,j) :
    if mp[i][j] : 
        q.append(mp[i][j])
        mp[i][j] = 0 
        
def merge(i,j,di,dj) :
	# 보드에 있는 칸들을 돌면서 
    while q :
        x = q.popleft()
        if not mp[i][j] :
            mp[i][j] = x 
        # 합쳐질수있다면
        elif mp[i][j] == x :
        	# 합친다
            mp[i][j] = x*2
            # 상하좌우에 맞춰서 di,dj를 더해준다.
            i,j = i+di,j+dj
        else :
        	# 다른 값이면 그냥 쌓인다.
            i,j = i + di,j+dj
            mp[i][j] = x 

def move(k) :
    # 상 
    if k == 0 :
        for j in range(n) :
            for i in range(n) :
                # q에 넣고 0으로 만든다. 
                get(i,j)
            # 0행 j열에서 부터 시작해서 몰아넣는다. 
            # 행이 1씩 증가하도록 한다. 
            merge(0,j,1,0) 
    # 하 
    elif k == 1 :
        for j in range(n) :
            for i in range(n-1,-1,-1) :
                get(i,j)
            # n-1행 j열에서부터 시작해서 몰아넣는다.
            # 행이 1씩 감소하도록 한다. 
            merge(n-1,j,-1,0)
    
    # 좌
    elif k ==2 :
        for i in range(n) :
            for j in range(n) :
                get(i,j)
            # i행 0열에서부터 시작해서 몰아넣는다.
            # 열이 1씩 증가하도록 한다. 
            merge(i,0,0,1)
    
    # 우
    else :
        for i in range(n) :
            for j in range(n-1,-1,-1) :
                get(i,j)
            # i행 n-1열 부터 시작해서 몰아넣는다.
            # 열이 1씩 감소하도록 한다. 
            merge(i,n-1,0,-1)


def solve(cnt) :
    global mp,ans
    if cnt == 5 :
        ans = max(ans,max(list(map(max,mp))))
        return 
    # 방향을 바꾸기전 mp을 저장 
    b = copy.deepcopy(mp)
    
    # 상하좌우 
    for k in range(4) :
        # mp를 변경 
        move(k)
        # 재귀, 한번 움직였으므로 cnt+1 
        solve(cnt+1)
        # 저장해두었던 방향을 바꾸기전 b를 다시 mp로 
        mp = copy.deepcopy(b)


if __name__=="__main__" :
    n = int(input())
    mp = [list(map(int,input().split()))for _ in range(n)]
    ans, q = 0, deque()

    solve(0)
    print(ans)

 

 

 

 

처음에 solve(0)을 호출한다.

여기서 0은 이동횟수다. 

 

 

solve(0)에서는 횟수를 보고 5번 움직였다면 보드에서 최댓값을 구해 ans에 저장한다.

5번 움직이기 전이라면 현재 mp를 b에 임시저장한다. 

블록을 움직이는 것은 상,하,좌,우 4방향으로 움직일 수 있으므로 for문을 돌면서 블록을 움직여준다. 

move(k) , k는 방향을 의미한다. 

 

 

move()는 인수로 들어온 방향에 따라 다르게 mp를 변경한다. 

일단 각칸에 블록이 있다면 해당 블록을 덱에 저장한다. 그리고 보드에는 0을 저장한다. 

상,하 라면 한 열의 탐색이 끝나면 merge를 하고 좌,우라면 한 행의 탐색이 끝나면 merge를 한다. 

 

 

merge()는 방향에 따라 인수를 다르게 준다.

merge의 인수는 i, j, di, dj이다. i,j는 초기위치, di,dj는 이동하는 방향이다. 

 

 

 

 

이렇게 쭉 DFS를 진행해주고 cnt ==5 가 되어 solve가 끝나면

mp = copy.deepcopy(b)를 하여 움직이기 전으로 보드를 만들어준다. 

 

 

 

---

 

Q. solve()함수에서 global mp를 하는데  왜 하는걸까??

 

 

 

def solve(cnt) :
    global mp,ans
    if cnt == 5 :
        ans = max(ans,max(list(map(max,mp))))
        return 
    # 방향을 바꾸기전 mp을 저장 
    b = copy.deepcopy(mp)
    
    # 상하좌우 
    for k in range(4) :
        # mp를 변경 
        move(k)
        # 재귀, 한번 움직였으므로 cnt+1 
        solve(cnt+1)
        # 저장해두었던 방향을 바꾸기전 b를 다시 mp로 
        mp = copy.deepcopy(b)

 

가장 마지막 줄 , mp = copy.deepcopy(b)에서 mp가 선언이 되어 지역List가 되기 때문이다.

이러면 b = copy.deepcopy(mp)에서 mp가 지역List이기 때문에 에러가 발생한다. 

 

 

그래서 global mp를 해주는 것이다!!!

 

이유  :  mp = copy.deepcopy(b)를 해서 mp가 지역List가 되버리기 때문 

 

 

 

 

 

 

참고 블로그 : 

https://jeongchul.tistory.com/667

백준 삼성 코딩 기출 문제 - 2048 (Easy) python