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

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

12100번: 2048 (Easy)

유형

브루트포스 , 백트래킹 , 구현 , 시뮬레이션

 

풀이

• 최대 5번 이동 시켜서 얻을 수 있는 가장 큰 블록을 출력한다
  • depth==5일 때 return
  • 상,하,좌,우로 브루트포스 백트래킹
• 시간제한 1초 , N의 크기는 최대 20
  • 4 ** 5 * (20*20) * 2 = 상하좌우 5번기회 , 전체가 다움직이고 , 백트래킹으로 다시 되돌리고
    • 다시 되돌리기 너무 힘드니까 , 애초에 move 할 때 copy 데이터를 사용하고 , 원본 데이터는 유지 시켜놓는다
  • (1000 ) X ( 800) = 8e5 → 시간 만족
  *주의) 필자는 시간복잡도 계산을 야매로 하기 때문에 틀릴 가능성이 큽니다… (믿지 마세요..)

---

코딩 전 대충 각 잡기 (생각의흐름)- 최종코드랑 다른 부분이 많을수도 적을수도 있습니다.

• 백트래킹 모듈 : dfs(인덱스)
• 상하좌우로 각 방향에 맞게 숫자들이 합쳐지는 모듈 move(방향) - 이게 어려움
  • 0,1,2,3은 상하좌우를 의미
  • def move(방향)
  • for i in range(n): for j in range(n): bfs_move(방향,i,j)
  • if data[i][j]!=0이면 bfs_move(방향,i,j)
    • def bfs_move(방향,x,y)
      • changed=[] : 합쳐진 좌표들은 여기에 추가
      • nx=x+dx[i] , ny=y+dy[i]
      • if nx가 영역 범위 안에 있고 , data[nx][ny]가 같은 값 , (nx,ny)not in changed :
        • 합친다
      • elif : nx,ny가 범위 안에 있고 , data[nx][ny]==0:
        • data[nx][ny]=data[x][y]
        • data[x][y]=0
        • queue에 nx,ny 넣기
• main
  • global max_value if n==5 : max_value 갱신 , break
  • for i in range(4) : deepocopy.copy(data), move(i,copy_data) , dfs(idx+1,move_copy_data,)

수정하기

1번째 move 완성

import copy
from collections import deque

n=int(input())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))

#상 하 좌 우
dx=[-1,1,0,0,]
dy=[0,0,-1,1]
def move(dir,data):
    for i in range(n):
        for j in range(n):
            if data[i][j]!=0:
                bfs_move(dir,i,j,data) # 방향 , 좌표
    return data

def bfs_move(dir,x,y,data):
    changed=[]
    q=deque([(dir,x,y)])
    while q:
        dir,x,y=q.popleft()

        nx=x+dx[dir]
        ny=y+dy[dir]

        if 0<=nx<n and 0<=ny<n and data[nx][ny]==data[x][y] and (nx,ny) not in changed:
            data[nx][ny]=data[x][y]*2 # 값 합치기
            data[x][y] = 0  # 원래 좌표는 0
            print('실행1')
        elif  0<=nx<n and 0<= ny < n and data[nx][ny]==0:
            data[nx][ny]=data[x][y]
            data[x][y]=0
            q.append((dir,nx,ny))
            print('실행2')

g=move(3,copy.deepcopy(graph))
print(g)

• 해당 예시에 대해서 상,좌는 잘되는데 하,우 move는 애매함
  • bfs가 (0,0) → (n-1,n-1)로 순차적으로 실행되어서 그럼
  • 마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. : 문제 중 이 조건이 현재 불만족이다

def move(dir,data):
    #상 좌는 (0,0)부터 순차적으로 탐색
    if dir==0 or dir==2:
        for i in range(n):
            for j in range(n):
                if data[i][j]!=0:
                    bfs_move(dir,i,j,data) # 방향 , 좌표

    else: #하 우는 (n-1,n-1)부터 역순을 퇌색
        for i in range(n-1,-1,-1):
            for j in range(n-1,-1,-1):
                if data[i][j]!=0:
                    bfs_move(dir, i, j, data)  # 방향 , 좌표

    return data

• 생각하기 힘들어서 단순하게 조건문으로 나누었다

첫 완성 코드

import copy
from collections import deque

n=int(input())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))

#상 하 좌 우
dx=[-1,1,0,0,]
dy=[0,0,-1,1]
def move(dir,data):
    #상 좌는 (0,0)부터 순차적으로 탐색
    if dir==0 or dir==2:
        for i in range(n):
            for j in range(n):
                if data[i][j]!=0:
                    bfs_move(dir,i,j,data) # 방향 , 좌표

    else: #하 우는 (n-1,n-1)부터 역순을 퇌색
        for i in range(n-1,-1,-1):
            for j in range(n-1,-1,-1):
                if data[i][j]!=0:
                    bfs_move(dir, i, j, data)  # 방향 , 좌표

    return data

def bfs_move(dir,x,y,data):
    changed=[]
    q=deque([(dir,x,y)])
    while q:
        dir,x,y=q.popleft()

        nx=x+dx[dir]
        ny=y+dy[dir]

        if 0<=nx<n and 0<=ny<n and data[nx][ny]==data[x][y] and (nx,ny) not in changed:
            data[nx][ny]=data[x][y]*2 # 값 합치기
            data[x][y] = 0  # 원래 좌표는 0

        elif  0<=nx<n and 0<= ny < n and data[nx][ny]==0:
            data[nx][ny]=data[x][y]
            data[x][y]=0
            q.append((dir,nx,ny))

max_value=0
def dfs(idx,data):
    global max_value
    if idx==5:
        for i in range(n):
            for j in range(n):
                max_value=max(max_value,data[i][j])
        return

    for i in range(4):
        moved_data=move(i,copy.deepcopy(data))
        dfs(idx+1,moved_data)

dfs(0,graph)
print(max_value)

• 테케는 통과인데 4퍼에서 틀림
• changed에 (nx,ny)를 추가 하는걸 깜박했다
• 그리고 changed가 bfs가 매번 실행될때마다 초기화 되는데 그러지 말고 한번 move 할 때 초기화된 changed리스트를 여러번 bfs가 실행되면서 공유가 되어야 한다

정답 코드

import copy
from collections import deque

n=int(input())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))

#상 하 좌 우
dx=[-1,1,0,0,]
dy=[0,0,-1,1]
def move(dir,data):
    #상 좌는 (0,0)부터 순차적으로 탐색
    changed=[]
    if dir==0 or dir==2:
        for i in range(n):
            for j in range(n):
                if data[i][j]!=0:
                    bfs_move(dir,i,j,data,changed) # 방향 , 좌표

    else: #하 우는 (n-1,n-1)부터 역순을 퇌색
        for i in range(n-1,-1,-1):
            for j in range(n-1,-1,-1):
                if data[i][j]!=0:
                    bfs_move(dir, i, j, data , changed)  # 방향 , 좌표

    return data

def bfs_move(dir,x,y,data,changed):
    
    q=deque([(dir,x,y)])
    while q:
        dir,x,y=q.popleft()

        nx=x+dx[dir]
        ny=y+dy[dir]

        if 0<=nx<n and 0<=ny<n and data[nx][ny]==data[x][y] and (nx,ny) not in changed:
            data[nx][ny]=data[x][y]*2 # 값 합치기
            data[x][y] = 0  # 원래 좌표는 0
            changed.append((nx,ny))

        elif  0<=nx<n and 0<= ny < n and data[nx][ny]==0:
            data[nx][ny]=data[x][y]
            data[x][y]=0
            q.append((dir,nx,ny))

max_value=0
def dfs(idx,data):
    global max_value
    if idx==5:
        for i in range(n):
            for j in range(n):
                max_value=max(max_value,data[i][j])
        return

    for i in range(4):
        moved_data=move(i,copy.deepcopy(data))
        dfs(idx+1,moved_data)

dfs(0,graph)
print(max_value)

⇒ 전체 흐름은 쉽지만 구현이 까다로운 문제다 , 시간은 좀 걸렸지만 다른 도움 없이 풀어서 뿌듯하다

⇒ 역시 구현 전에 어떻게 구현 할 지 각을 미리 재고 , 어떻게 할지 작성하고 구현하는게 훨씬 편하고 머리가 덜 복잡해진다

⇒ 미리 각 잴 때 , 어떤 모듈을 만들어야 하고 각 모듈의 파라미터랑 return값은 무엇인지 설계하는게 중요하다