106. [삼성기출2] Python 백준 12100 번 2048 (Easy)자세한 설명

Notice

Recent Posts

Recent Comments

Link

« 2025/07 »
일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

코딩하는 덕구 🐶

106. [삼성기출2] Python 백준 12100 번 2048 (Easy)자세한 설명 본문

알고리즘 문제 풀이

106. [삼성기출2] Python 백준 12100 번 2048 (Easy)자세한 설명

코딩하는 덕구 🐶 2023. 3. 17. 15:26

728x90

안녕하세요 코딩하는 덕구입니다.

브루트포스 문제인 백준 12100 번 2048(Easy) 입니다.

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

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

먼저 백준 12100 번 2048(Easy) 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

from copy import deepcopy
N = int(input())
board = []
for i in range(N):
    board.append(list(map(int, input().split())))

def find_max(board, cnt): #최대 숫자 탐색
    global ans
    if cnt == 5:
        for i in range(N):
            for j in range(N):
                ans = max(ans, board[i][j])
        return

    for dir in range(4): #상 하 좌 우 이동
        find_max(move(deepcopy(board), dir), cnt + 1) #deep copy안하면 보드 원본이 바뀜

def move(board, dir): #상 하 좌 우 이동한 보드를 return 해주는 함수
    if dir == 0: #상
        for j in range(N):
            ptr = 0
            for i in range(1, N): #1부터 모든 블럭 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[ptr][j] == 0: #ptr이 0이면
                        board[ptr][j] = tmp
                    elif board[ptr][j] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[ptr][j] *= 2
                        ptr += 1
                    else: #ptr이 다르면
                        ptr += 1 #ptr 하나 올려주고
                        board[ptr][j] = tmp #그 위치에 값을 옮겨줌

    elif dir == 1: #하
        for j in range(N):
            ptr = N-1
            for i in range(N-2, -1, -1): #N-2 부터 모든 블럭 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[ptr][j] == 0: #ptr이 0이면
                        board[ptr][j] = tmp
                    elif board[ptr][j] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[ptr][j] *= 2
                        ptr -= 1
                    else: #ptr이 다르면
                        ptr -= 1 #ptr 하나 내려주고
                        board[ptr][j] = tmp #그 위치에 값을 옮겨줌

    elif dir == 2: #좌
        for i in range(N): #0 행부터 N-1 행까지 하나씩 검사
            ptr = 0
            for j in range(1, N): #1 열부터 N-1 열까지 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][ptr] == 0: #ptr이 0이면
                        board[i][ptr] = tmp
                    elif board[i][ptr] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[i][ptr] *= 2
                        ptr += 1
                    else: #ptr이 다르면
                        ptr += 1 #ptr 하나 올려주고
                        board[i][ptr] = tmp #그 위치에 값을 옮겨줌

    else: #우
        for i in range(N):  # 0 행부터 N-1 행까지 하나씩 검사
            ptr = N-1
            for j in range(N-2, -1, -1):  #N-2 열 부터 0 열 까지 검사
                if board[i][j]:  # 보드에 성분이 있을 때 성분 저장 후 해당 블럭 0으로 변경
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][ptr] == 0:  # ptr이 0이면
                        board[i][ptr] = tmp
                    elif board[i][ptr] == tmp:  # ptr이 검사하는 블럭과 같으면
                        board[i][ptr] *= 2
                        ptr -= 1
                    else:  # ptr이 다르면
                        ptr -= 1  # ptr 하나 내려주고
                        board[i][ptr] = tmp  # 그 위치에 값을 옮겨줌
    return board

ans = 0
find_max(board, 0)
print(ans)

문제 요약

2048 게임에서 보드의 상태가 주어지면

5번 이동후에 만들 수 있는 가장 큰 수를 구하시오

문제 접근

상, 하, 좌, 우 4방향으로 5번 이동하면 4^5 = 2^10 = 1024

1024 가지의 경우의 수만 살펴보면 되므로 모든 경우를 탐색하여 가장 큰 숫자를 출력합니다.

Python 코드 구현

먼저 보드의 세로, 가로 길이인 N 과 보드를 입력받습니다.

N = int(input())

board = []
for i in range(N):
    board.append(list(map(int, input().split())))

보드 5번 이동시 최대 숫자를 탐색할 함수 find_max를 선언합니다.

def find_max(board, cnt): #최대 숫자 탐색
    global ans
    if cnt == 5:
        for i in range(N):
            for j in range(N):
                ans = max(ans, board[i][j])
        return

    for dir in range(4): #상 하 좌 우 이동
        find_max(move(deepcopy(board), dir), cnt + 1) #deep copy안하면 보드 원본이 바뀜

cnt 는 보드 이동 횟수를 저장하는 변수이고,

보드가 5번 이동하면(cnt == 5) 모든 보드의 성분 중 가장 큰 숫자를 찾고 함수를 종료합니다.

move 함수입니다. 편의상 위로 움직일 때만 설명합니다.

def move(board, dir): #상 하 좌 우 이동한 보드를 return 해주는 함수
    if dir == 0: #상
        for j in range(N):
            ptr = 0
            for i in range(1, N): #1부터 모든 블럭 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[ptr][j] == 0: #ptr이 0이면
                        board[ptr][j] = tmp
                    elif board[ptr][j] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[ptr][j] *= 2
                        ptr += 1
                    else: #ptr이 다르면
                        ptr += 1 #ptr 하나 올려주고
                        board[ptr][j] = tmp #그 위치에 값을 옮겨줌

2048 게임에서 위로 동작시키면 같은 수 끼리 합쳐지고, 숫자가 다르면 합쳐지지 않습니다.

또한 위가 비어있다면 아래 방향으로 가장 가까운 수가 그 자리로 이동하게 되죠 (합쳐질 수 있으면 합쳐지면서 이동합니다.)

2 0 0

4 0 0

예를들어 보드가 위 와 같은 상황이고 빈 칸을 0 이라고 생각하면, 해당 보드를 위로 움직이면

4 0 0

0 0 0 이렇게 됩니다. 이제 구현해봅시다.

구현하기 위해 규칙의 기준이 되는 지점 ptr을 구현해줍니다. (포인터)

i는 세로, j는 가로의 좌표를 의미하는데 위로 이동하므로 j를 바깥 for문에 넣어주고

i는 1부터 N-1 까지 이동하며 검사해줍니다.

또한 가로 줄 마다 기준점이 다르므로 j 의 반복마다 ptr을 맨 위의 점으로 초기화 해줍니다.

for j in range(N):
    ptr = 0
    for i in range(1, N): #1부터 모든 블럭 검사

모든 좌표를 탐색하며 성분이 있다면 저장하고 해당 좌표의 숫자는 이동할것이므로 0으로 만들어줍니다.

if board[i][j]: #보드에 성분이 있을 때
    tmp = board[i][j]
    board[i][j] = 0

세 가지의 경우가 있습니다.

기준점이 비어있는 경우, 기준점이 탐색한 좌표의 숫자와 같은경우, 기준점이 탐색한 숫자와 다른 경우

기준점이 0인경우 좌표에 있던 성분을 기준점에 저장합니다.

if board[ptr][j] == 0: #ptr이 0이면
    board[ptr][j] = tmp

기준점이 탐색 좌표와 같다면 두 숫자를 더합니다. 같은 수를 더하는 것은 곱하기 2와 같습니다.

그리고 한번 더 해지면 다시한번 더할 수 없으므로 기준점의 좌표에 1 더해줍니다. (세로로 위에서 아래로 하나 내림)

elif board[ptr][j] == tmp: #ptr이 검사하는 블럭과 같으면
    board[ptr][j] *= 2
    ptr += 1

기준점이 탐색 좌표와 다르다면 기준점 위에 탐색 좌표의 숫자를 저장합니다.

else: #ptr이 다르면
    ptr += 1 #ptr 하나 올려주고
    board[ptr][j] = tmp #그 위치에 값을 옮겨줌

위에 까지 잘 따라 오셨다면 코드와 주석만 보고 이해하실 수 있으실 겁니다.

보드와 이동 방향을 입력받고 해당 방향으로 이동한 보드를 출력하는 함수인 move를 작성했습니다.

def move(board, dir): #상 하 좌 우 이동한 보드를 return 해주는 함수
    if dir == 0: #상
        for j in range(N):
            ptr = 0
            for i in range(1, N): #1부터 모든 블럭 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[ptr][j] == 0: #ptr이 0이면
                        board[ptr][j] = tmp
                    elif board[ptr][j] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[ptr][j] *= 2
                        ptr += 1
                    else: #ptr이 다르면
                        ptr += 1 #ptr 하나 올려주고
                        board[ptr][j] = tmp #그 위치에 값을 옮겨줌

    elif dir == 1: #하
        for j in range(N):
            ptr = N-1
            for i in range(N-2, -1, -1): #N-2 부터 모든 블럭 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[ptr][j] == 0: #ptr이 0이면
                        board[ptr][j] = tmp
                    elif board[ptr][j] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[ptr][j] *= 2
                        ptr -= 1
                    else: #ptr이 다르면
                        ptr -= 1 #ptr 하나 내려주고
                        board[ptr][j] = tmp #그 위치에 값을 옮겨줌

    elif dir == 2: #좌
        for i in range(N): #0 행부터 N-1 행까지 하나씩 검사
            ptr = 0
            for j in range(1, N): #1 열부터 N-1 열까지 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][ptr] == 0: #ptr이 0이면
                        board[i][ptr] = tmp
                    elif board[i][ptr] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[i][ptr] *= 2
                        ptr += 1
                    else: #ptr이 다르면
                        ptr += 1 #ptr 하나 올려주고
                        board[i][ptr] = tmp #그 위치에 값을 옮겨줌

    else: #우
        for i in range(N):  # 0 행부터 N-1 행까지 하나씩 검사
            ptr = N-1
            for j in range(N-2, -1, -1):  #N-2 열 부터 0 열 까지 검사
                if board[i][j]:  # 보드에 성분이 있을 때 성분 저장 후 해당 블럭 0으로 변경
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][ptr] == 0:  # ptr이 0이면
                        board[i][ptr] = tmp
                    elif board[i][ptr] == tmp:  # ptr이 검사하는 블럭과 같으면
                        board[i][ptr] *= 2
                        ptr -= 1
                    else:  # ptr이 다르면
                        ptr -= 1  # ptr 하나 내려주고
                        board[i][ptr] = tmp  # 그 위치에 값을 옮겨줌
    return board

이제 정답 변수인 ans 를 초기화하고 find_max를 실행하고, ans를 출력합니다.

ans = 0
find_max(board, 0)
print(ans)

백준 12100 번 2048(easy) 최종 코드입니다.

from copy import deepcopy

N = int(input())
board = []
for i in range(N):
    board.append(list(map(int, input().split())))

def find_max(board, cnt): #최대 숫자 탐색
    global ans
    if cnt == 5:
        for i in range(N):
            for j in range(N):
                ans = max(ans, board[i][j])
        return

    for dir in range(4): #상 하 좌 우 이동
        find_max(move(deepcopy(board), dir), cnt + 1) #deep copy안하면 보드 원본이 바뀜

def move(board, dir): #상 하 좌 우 이동한 보드를 return 해주는 함수
    if dir == 0: #상
        for j in range(N):
            ptr = 0
            for i in range(1, N): #1부터 모든 블럭 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[ptr][j] == 0: #ptr이 0이면
                        board[ptr][j] = tmp
                    elif board[ptr][j] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[ptr][j] *= 2
                        ptr += 1
                    else: #ptr이 다르면
                        ptr += 1 #ptr 하나 올려주고
                        board[ptr][j] = tmp #그 위치에 값을 옮겨줌

    elif dir == 1: #하
        for j in range(N):
            ptr = N-1
            for i in range(N-2, -1, -1): #N-2 부터 모든 블럭 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[ptr][j] == 0: #ptr이 0이면
                        board[ptr][j] = tmp
                    elif board[ptr][j] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[ptr][j] *= 2
                        ptr -= 1
                    else: #ptr이 다르면
                        ptr -= 1 #ptr 하나 내려주고
                        board[ptr][j] = tmp #그 위치에 값을 옮겨줌

    elif dir == 2: #좌
        for i in range(N): #0 행부터 N-1 행까지 하나씩 검사
            ptr = 0
            for j in range(1, N): #1 열부터 N-1 열까지 검사
                if board[i][j]: #보드에 성분이 있을 때
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][ptr] == 0: #ptr이 0이면
                        board[i][ptr] = tmp
                    elif board[i][ptr] == tmp: #ptr이 검사하는 블럭과 같으면
                        board[i][ptr] *= 2
                        ptr += 1
                    else: #ptr이 다르면
                        ptr += 1 #ptr 하나 올려주고
                        board[i][ptr] = tmp #그 위치에 값을 옮겨줌

    else: #우
        for i in range(N):  # 0 행부터 N-1 행까지 하나씩 검사
            ptr = N-1
            for j in range(N-2, -1, -1):  #N-2 열 부터 0 열 까지 검사
                if board[i][j]:  # 보드에 성분이 있을 때 성분 저장 후 해당 블럭 0으로 변경
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][ptr] == 0:  # ptr이 0이면
                        board[i][ptr] = tmp
                    elif board[i][ptr] == tmp:  # ptr이 검사하는 블럭과 같으면
                        board[i][ptr] *= 2
                        ptr -= 1
                    else:  # ptr이 다르면
                        ptr -= 1  # ptr 하나 내려주고
                        board[i][ptr] = tmp  # 그 위치에 값을 옮겨줌
    return board

ans = 0
find_max(board, 0)
print(ans)

백준 12100 번 2048(easy) 자세한 설명 및 Python 코드였습니다.

감사합니다.

728x90

저작자표시 (새창열림)

'알고리즘 문제 풀이' 카테고리의 다른 글

108. [삼성기출4] Python 백준 13458 번 시험 감독 자세한 설명 (0)	2023.03.18
107. [삼성기출3] Python 백준 3190 번 뱀 자세한 설명 (0)	2023.03.18
105. [삼성기출1] Python 백준 13460 번 구슬 탈출 2 자세한 설명 (0)	2023.03.16
101. 인공지능 기초 (2) AI, ML, DL, 인공지능 기초 용어 (0)	2023.02.06
100. 인공지능 기초 (1) 인공지능 필수 기초 수학 (0)	2023.01.28

'알고리즘 문제 풀이' Related Articles

코딩하는 덕구 🐶

106. [삼성기출2] Python 백준 12100 번 2048 (Easy)자세한 설명 본문

106. [삼성기출2] Python 백준 12100 번 2048 (Easy)자세한 설명

문제 요약

문제 접근

Python 코드 구현

'알고리즘 문제 풀이' 카테고리의 다른 글

티스토리툴바