[BJ12100] 2048 (Easy)

🚩 문제 설명

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

12100번: 2048 (Easy)

 

⏱️ 시간 복잡도
▪각 방향으로 움직이면 x 4
▪각 블록을 돈다면 4N^2
▪카운팅이 5번 이하이므로 20N^2 = O(N^2)

◾ 최대 5번 움직일 수 있습니다.

◾ 한번 이동할 때, 합쳐진 블록은 다시 합칠 수는 없습니다.

◾ 전체블록을 상/하/좌/우 네 방향으로 움직일 수 있습니다.

◾ 최대 5번 움직여서 만들 수 있는 가장 큰 블록의 값을 구하는 문제.

 

 

 

---

 

 

 

✅ 입출력

1. n : 보드의 크기 (n x n)
2. n 개의 줄 : 보드 초기화 상태
return ➡️ 최대 5번 이동하여 만들 수 있는 가장 큰 블록의 값

✔️ 예제 1

3
2 2 2
4 4 4
8 8 8

16

 

✔️ 예제 2

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

4

 

✔️ 예제 3

4
2 4 16 8
8 4 0 0
16 8 2 0
2 8 2 0

32

 

✔️ 예제 4

4
2 4 8 2
2 4 0 0
2 0 0 0
2 0 2 0

16

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from copy import deepcopy
from collections import deque

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

# 보드의 크기
n = int(input())
# 보드 입력
a = [list(map(int, input().split())) for _ in range(n)]
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 큐에 넣기
def get(i, j):
    # 0이 아니라면 큐에 넣는다
    if a[i][j]:
        q.append(a[i][j])
        a[i][j] = 0  # 올바른 합을 하기위해서 0으로 초기화


# bfs 로 인접한 값과 비교하기
# a[i][j] : 타겟값
def bfs(i, j, x, y):
    while q:
        tmp = q.popleft()
        # 타겟값이 0일때 - 타겟값 이동 x
        if not a[i][j]:
            a[i][j] = tmp
        # 타겟값과 같을때 - 더한다.
        elif a[i][j] == tmp:
            a[i][j] = tmp * 2
            i += x
            j += y
        # 타겟값과 같지않을때 - 타겟값 이동
        else:
            i += x
            j += y
            a[i][j] = tmp


# 상하좌우 움직이기
def move(k):
    # 상
    if k == 0:
        for i in range(n):
            for j in range(n):
                # 위 -> 아래 큐에 넣기
                get(j, i)
            # 행, 열, -1, 0 : 아래로 더해져간다.
            # 행이 0인 이유는 dx[k+1] 이 더해지면서 이동하므로
            # 열이 i인 이유는 각 열마다 처리해야하므로
            bfs(0, i, dx[k + 1], dy[k + 1])
    # 하
    elif k == 1:
        for i in range(n):
            for j in reversed(range(n)):
                # 아래 -> 위 큐에 넣기
                get(j, i)
            # 위로 더해져간다.
            bfs(n - 1, i, dx[k - 1], dy[k - 1])
    # 좌
    elif k == 2:
        for i in range(n):
            for j in range(n):
                # 좌 -> 우 큐에 넣기
                get(i, j)
            # 오른쪽에서부터 더해져간다.
            bfs(i, 0, dx[k + 1], dy[k + 1])
    # 우
    else:
        for i in range(n):
            for j in reversed(range(n)):
                # 우 -> 좌 큐에 넣기
                get(i, j)
            # 왼쪽에서부터 더해져간다.
            bfs(i, n - 1, dx[k - 1], dy[k - 1])


def dfs(cnt):
    global a, ans
    if cnt == 5:  # 최대 5번까지 움직였다면
        ans = max(ans, max(map(max, a)))
        return

    a_ = deepcopy(a)  # 방향을 바꾸기 전에 원래의 보드를 기억해야 한다.

    for k in range(4):  # 4방향으로 움직인다.
        move(k)  # 움직인다.
        dfs(cnt + 1)  # 재귀적으로 호출한다.
        a = deepcopy(a_)


if __name__ == '__main__':
    q = deque()  # 큐 생성
    cnt = 0  # 카운팅
    ans = 0
    dfs(cnt)
    print(ans)

💬 Point

➡️  큐를 이용하여 각 방향의 블록을 넣고 타겟값과 비교한다.
➡️  상하좌우 각각 경우를 나누어 생각한다.

◾ 어려워보이지만 일단 두려워말고 각 경우를 잘 나눠 생각해봅시다..

◾ DFS/BFS

https://yeomss.tistory.com/138?category=832773 

[BJ1260] DFS와 BFS

def dfs(v):
    visited[v] = 1
    print(v, end=' ')

    for i in graph[v]:
        if visited[i] == 0:
            dfs(i)

DFS를 텍스트로 구조화한다면 다음과 같습니다.

1. 방문 처리
2. print()
3. for문 - 그래프돌기
    1) 방문하지않았다면 dfs() 재귀 호출

 

◾ 입력값들을 입력 받습니다.

# 보드의 크기
n = int(input())
# 보드 입력
a = [list(map(int, input().split())) for _ in range(n)]
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

 

◾ 상하좌우로 움직일 때 사용하는 함수를 작성합니다.

두개의 for문을 돌아 보드에 들어있는 값들을 각각 타겟값으로 정합니다.

해당 블록들을 큐에 넣기 위하여 get() 이라는 함수를 작성합니다.

# 상하좌우 움직이기
def move(k):
    # 상
    if k == 0:
        for i in range(n):
            for j in range(n):
                # 위 -> 아래 큐에 넣기
                get(j, i)
            # 행, 열, -1, 0 : 아래로 더해져간다.
            # 행이 0인 이유는 dx[k+1] 이 더해지면서 이동하므로
            # 열이 i인 이유는 각 열마다 처리해야하므로
            bfs(0, i, dx[k + 1], dy[k + 1])
    # 하
    elif k == 1:
        for i in range(n):
            for j in reversed(range(n)):
                # 아래 -> 위 큐에 넣기
                get(j, i)
            # 위로 더해져간다.
            bfs(n - 1, i, dx[k - 1], dy[k - 1])
    # 좌
    elif k == 2:
        for i in range(n):
            for j in range(n):
                # 좌 -> 우 큐에 넣기
                get(i, j)
            # 오른쪽에서부터 더해져간다.
            bfs(i, 0, dx[k + 1], dy[k + 1])
    # 우
    else:
        for i in range(n):
            for j in reversed(range(n)):
                # 우 -> 좌 큐에 넣기
                get(i, j)
            # 왼쪽에서부터 더해져간다.
            bfs(i, n - 1, dx[k - 1], dy[k - 1])

 

◾ 만약 0이 아니라면 큐에 넣습니다. (0은 빈 블록을 의미합니다. 따라서 큐에 넣지않습니다.)

bfs() 를 사용하기 위해서 큐에 넣습니다. 인접한 값들을 사용해야 하기 때문입니다.

올바른 합을 구하기 위하여 일단 0으로 해당 값의 블록을 초기화해줍니다.

# 큐에 넣기
def get(i, j):
    # 0이 아니라면 큐에 넣는다
    if a[i][j]:
        q.append(a[i][j])
        a[i][j] = 0  # 올바른 합을 하기위해서 0으로 초기화

 

◾ q가 남아있지 않을 때 까지, while 문을 돕니다.

큐에는 (상) 이면 위에서 아래로 값들이 저장되고,

(하) 면 아래에서 위로 값들이 저장되고, (좌) 면 좌에서 우로 값들이 저장되고, (우) 면 우에서 좌로 값들이 저장됩니다.

이 값들은 타겟값과 비교되어 해당 블록에 올바른 값이 저장됩니다.

만약 타겟값이 0이면 그대로 원래의 값을 저장합니다.

그렇지 않고 타겟값이 같다면, 예를 들어 2와 2가 만났다면 더한 값을 넣습니다. 그리고 값은 더해졌으므로 타겟값은 이동합니다.

이동할 때는 x, y 값을 더합니다. 이는 dx, dy 에서 꺼냅니다.

만약 타겟값과 같지 않다면 그냥 저장되는 값없이 타겟값이 이동됩니다.

# bfs 로 인접한 값과 비교하기
# a[i][j] : 타겟값
def bfs(i, j, x, y):
    while q:
        tmp = q.popleft()
        # 타겟값이 0일때 - 타겟값 이동 x
        if not a[i][j]:
            a[i][j] = tmp
        # 타겟값과 같을때 - 더한다.
        elif a[i][j] == tmp:
            a[i][j] = tmp * 2
            i += x
            j += y
        # 타겟값과 같지않을때 - 타겟값 이동
        else:
            i += x
            j += y
            a[i][j] = tmp

 

◾ global a, ans 을 하여 전역변수를 해당 스코프에서도 사용하게 합니다.

만약 최대 5번까지 움직였다면 재귀에서 빠져나옵니다.

max(map(max, a)) 를 해서 2차원 배열 중에서 최댓값을 찾습니다.

예를 들어 a = [[1,2,3], [4,5,6]] 이 있다면 map(max, a) 는 [3, 6] 이 됩니다.

여기서 한번 더 max() 를 하면 max(map(max, a)) 를 하면 [6] 이 나옵니다.

해당 값과 다시한번 이때까지의 ans 를 비교합니다. 따라서 ans = max(ans, max(map(max, a))) 가 되는 것 입니다.

방향을 바꾸기 전 원래의 보드를 기억하기 위해서 deepcopy() 함수를 사용하여 복사를 해줍니다.

상하좌우로 움직이기 위해서 for문 4번을 돕니다. 각 방향으로 계속 움직여서 카운팅을 해줍니다. 카운팅이 5가 되면 빠져나옵니다.

그리고 재귀호출이 끝나면 다시 a 를 복원시켜 줘야합니다. 이전에 저장해놓았던 값으로 할당해줍니다.

def dfs(cnt):
    global a, ans
    if cnt == 5:  # 최대 5번까지 움직였다면
        ans = max(ans, max(map(max, a)))
        return

    a_ = deepcopy(a)  # 방향을 바꾸기 전에 원래의 보드를 기억해야 한다.

    for k in range(4):  # 4방향으로 움직인다.
        move(k)  # 움직인다.
        dfs(cnt + 1)  # 재귀적으로 호출한다.
        a = deepcopy(a_)

 

 

 

 

 

 

 

# 알고리즘 백준 2048 파이썬

# 알고리즘 BJ12100 2048(Easy) python

---