# 12100-2048

[www.acmicpc.net/problem/12100](https://www.acmicpc.net/problem/12100)

1. 매 시도마다 4 방향을 모두 DFS 로 재귀를 타줘야 한다.
2. 상, 하, 좌, 우 로 몰아주는 매열 수정을 구현한다.
3. 5번 수행하고 나면 매번 배열 중 가장 큰 값을 최댓값 업데이트 해준다.

```python
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

# 우, 좌, 상, 하
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

''''''
def dfs(time, a, dir):
    global max_ans, n
    if time >= 5:
        for i in range(n):
            max_ans = max(max_ans, max(a[i]))
        return

    na = [[0 for _ in range(n)] for _ in range(n)]
    # dir 에 따라 이동수행하여 a 기준으로 na 를 할당하자
    '''
    a 를 보고, dir 에 따라서 스택을 쌓아가자
    dir 이 상, 하 인 것과 좌, 우 인걸 두개로 구분해서 처리하자

    '''
    if dir == 0:
        for i in range(len(a)):
            stack = []
            rst = []
            for j in range(len(a)):
                if a[i][n - 1 - j]:
                    stack.append(a[i][n - 1 - j])
                # 두번째 부터는
                if len(stack) >= 2:
                    # 새로들어온게 같으면
                    if stack[-1] == stack[-2]:
                        # 같은거 2배해준거 따로 저장해주고
                        together = stack[-1] * 2
                        # 스택에서 뒤에 두개 빼주고
                        stack.pop()
                        stack.pop()
                        # 2배해준거 스택에 더해주고
                        stack.append(together)
                        # 몽땅 rst 에 추가
                        rst.extend(stack[:])
                        stack = []
            # 배치할 rst 를 완벽히 만들었당
            rst.extend(stack[:])
            loc = 0
            for v in rst:
                na[i][n - loc - 1] = v
                loc += 1

    elif dir == 1:
        for i in range(len(a)):
            stack = []
            rst = []
            for j in range(len(a)):
                if a[i][j]:
                    stack.append(a[i][j])
                # 두번째 부터는
                if len(stack) >= 2:
                    # 새로들어온게 같으면
                    if stack[-1] == stack[-2]:
                        # 같은거 2배해준거 따로 저장해주고
                        together = stack[-1] * 2
                        # 스택에서 뒤에 두개 빼주고
                        stack.pop()
                        stack.pop()
                        # 2배해준거 스택에 더해주고
                        stack.append(together)
                        # 몽땅 rst 에 추가
                        rst.extend(stack[:])
                        stack = []
            # 배치할 rst 를 완벽히 만들었당
            rst.extend(stack[:])
            loc = 0
            for v in rst:
                na[i][loc] = v
                loc += 1

    elif dir == 2:
        for i in range(len(a)):
            stack = []
            rst = []
            for j in range(len(a)):
                if a[j][i]:
                    stack.append(a[j][i])
                # 두번째 부터는
                if len(stack) >= 2:
                    # 새로들어온게 같으면
                    if stack[-1] == stack[-2]:
                        # 같은거 2배해준거 따로 저장해주고
                        together = stack[-1] * 2
                        # 스택에서 뒤에 두개 빼주고
                        stack.pop()
                        stack.pop()
                        # 2배해준거 스택에 더해주고
                        stack.append(together)
                        # 몽땅 rst 에 추가
                        rst.extend(stack[:])
                        stack = []
            # 배치할 rst 를 완벽히 만들었당
            rst.extend(stack[:])
            loc = 0
            for v in rst:
                na[loc][i] = v
                loc += 1

    elif dir == 3:
        for i in range(len(a)):
            stack = []
            rst = []
            for j in range(len(a)):
                if a[n - j - 1][i]:
                    stack.append(a[n - j - 1][i])
                # 두번째 부터는
                if len(stack) >= 2:
                    # 새로들어온게 같으면
                    if stack[-1] == stack[-2]:
                        # 같은거 2배해준거 따로 저장해주고
                        together = stack[-1] * 2
                        # 스택에서 뒤에 두개 빼주고
                        stack.pop()
                        stack.pop()
                        # 2배해준거 스택에 더해주고
                        stack.append(together)
                        # 몽땅 rst 에 추가
                        rst.extend(stack[:])
                        stack = []
            # 배치할 rst 를 완벽히 만들었당
            rst.extend(stack[:])
            loc = 0
            for v in rst:
                na[n - loc - 1][i] = v
                loc += 1

    time += 1
    for i in range(4):
        dfs(time, na, i)
''''''

time = 0
max_ans = 2
for i in range(4):
    dfs(time, a, i)

print(max_ans)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://pyohamen.gitbook.io/til/algorithm/boj/12100-2048.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.