Posts [baekjoon] 12100. 2048(Easy) (python)
Post
Cancel

[baekjoon] 12100. 2048(Easy) (python)

Feb 1, 2021 2021-02-01T11:10:00+09:00 by youbin
9 min

12100. 2048(Easy) 문제 바로가기

해결 방법

  1. board 에 초기 입력값을 이중 리스트로 저장한다.

  2. move_ways 에 4가지 방향에 대한 5번의 가능한 이동 방법을 중복 순열을 이용하여 저장한다.

    • 4가지 방향에 대해

      왼쪽: 0, 오른쪽: 1, 위: 2, 아래: 3 으로 하였다.

  3. move_ways 에 저장된 이동 방법을 하나씩 test_board 에 5번 이동시켜 가장 큰 블록이 있는지 확인한다.

함수 동작 과정

rightBlock 과정

  1. 행을 확인하며 합이 0이 아닌 경우 체크한다.

    • 합이 0인 경우는 행의 원소가 모두 0이라는 것이기에 변화가 일어날 일이 없기에 가지치기!

  2. 행의 뒤의 인덱스부터 확인한다. 이때 앞의 인덱스(c) 와 그 앞의 인덱스(c2)들을 모두 확인하도록 한다.

    • 이때 c2 가 0이 아닌 경우! break 한다. → 0이 아닌 인접한 인덱스와 비교해야하기 때문!!
      • c의 위치의 값(num1)과 c2의 위치의 값(num2)이 같으면 num1에 2를 곱하고 c2 위치의 값은 0으로 만든다.

  3. 숫자 사이에 0이 없애기

    1. 행에 존재하는 0을 모두 지우기

      ※ 주의 : 인덱스를 뒤에서 부터 확인해야 한다! 리스트 pop을 할 때 앞에서 부터 한다면 IndexError가 발생할 수 있다.

    2. 지워진 0의 개수만큼 행 뒤에 0을 추가하기

leftBlock 과정

  1. 행을 확인하며 합이 0이 아닌 경우 체크한다.

    • 합이 0인 경우는 행의 원소가 모두 0이라는 것이기에 변화가 일어날 일이 없기에 가지치기!

  2. 행의 앞의 인덱스부터 확인한다. 이때 앞의 인덱스(c) 와 그 뒤의 인덱스(c2)들을 모두 확인하도록 한다.

    • 이때 c2 가 0이 아닌 경우! break 한다. → 0이 아닌 인접한 인덱스와 비교해야하기 때문!!
      • c의 위치의 값(num1)과 c2의 위치의 값(num2)이 같으면 num1에 2를 곱하고 c2 위치의 값은 0으로 만든다.

  3. 숫자 사이에 0이 없애기

    1. 행에 존재하는 0을 모두 지우기

      ※ 주의 : 인덱스를 뒤에서 부터 확인해야 한다! 리스트 pop을 할 때 앞에서 부터 한다면 IndexError가 발생할 수 있다.

    2. 지워진 0의 개수만큼 행 뒤에 0을 추가하기

블록을 이동시키는 구현 방법

  1. 왼쪽으로 미는 경우 : leftBlock 함수 이용

  2. 오른쪽으로 미는 경우 : rightBlock 함수 이용

  3. 위쪽으로 미는 경우

    위쪽으로 밀기 == 시계방향으로 90도 돌리고 오른쪽으로 밀기

    turn_board에 test_board 를 시계방향으로 90도 회전하여 저장한다.

    turn_board 를 rightBlock 함수를 통해 오른쪽으로 밀고 test_board에 시계 방향으로 270도 회전하여 저장한다. → 다시 원방향(90도 + 270도 = 360도)으로 복구하여 저장!

  4. 아래쪽으로 미는 경우

    아래쪽으로 밀기 == 시계방향으로 90도 돌리고 왼쪽으로 밀기

    turn_board에 test_board 를 시계방향으로 90도 회전하여 저장한다.

    turn_board 를 leftBlock 함수를 통해 왼쪽으로 밀고 test_board에 시계 방향으로 270도 회전하여 저장한다. → 다시 원방향(90도 + 270도 = 360도)으로 복구하여 저장!

구현한 코드

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

from itertools import product # 중복 순열
from copy import deepcopy

def rightBlock(t_board):
    # 같은 수를 만나면 2 곱해주기
    for r in range(N):
        if sum(t_board[r]) != 0:
            for c in range(N - 1, 0, -1):
                if t_board[r][c] != 0:
                    num1 = t_board[r][c]
                    change_idx = 0
                    num2 = -1
                    for c2 in range(c - 1, -1, -1):
                        if t_board[r][c2] != 0:
                            num2 = t_board[r][c2]
                            change_idx = c2
                            break
                    if num2 == num1: # 같은 수인 경우
                        t_board[r][c] *= 2
                        t_board[r][change_idx] = 0
    # 숫자 사이에 0이 없도록 땡기기
    for r in range(N):
        if sum(t_board[r]) != 0:
            for c in range(N - 1, -1, -1):
                if t_board[r][c] == 0: # 행에 존재하는 0을 지우기
                    t_board[r].pop(c)
            while len(t_board[r]) < N: # 지워진 0만큼 행 앞에 추가하기
                t_board[r].insert(0, 0)


def leftBlock(t_board):
    # 같은 수를 만나면 2 곱해주기
    for r in range(N):
        if sum(t_board[r]) != 0:
            for c in range(N - 1):
                if t_board[r][c] != 0:
                    num1 = t_board[r][c]
                    change_idx = 0
                    num2 = -1
                    for c2 in range(c + 1, N):
                        if t_board[r][c2] != 0:
                            num2 = t_board[r][c2]
                            change_idx = c2
                            break
                    if num2 == num1: # 같은 수인 경우
                        t_board[r][c] *= 2
                        t_board[r][change_idx] = 0
    # 숫자 사이에 0이 없도록 땡기기
    for r in range(N):
        if sum(t_board[r]) != 0:
            for c in range(N - 1, -1, -1): # 행에 존재하는 0을 지우기
                if t_board[r][c] == 0:
                    t_board[r].pop(c)
            while len(t_board[r]) < N: # 지워진 0을 뒤에 추가하기
                t_board[r].append(0)


N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
max_block = 0 # 가장 큰 블록을 저장할 변수, 출력할 값
# move_ways : 4가지 방향(위, 아래, 왼쪽, 오른쪽)에 대한 모든 5번 이동하는 모든 경우의 수를 저장한 리스트 (중복 순열 이용)
move_ways = list(product(range(4), repeat=5))

for m_list in move_ways: # 완전 탐색
    test_board = deepcopy(board) # 5번의 이동을 저장할 리스트
    for m in m_list:
        if m == 0: # 왼쪽으로 미는 경우
            leftBlock(test_board)

        elif m == 1: # 오른쪽으로 미는 경우
            rightBlock(test_board)

        elif m == 2: # 위로 미는 경우 (시계방향으로 90도 회전시키고 오른쪽으로 밀기)
            turn_board = [[0] * N for _ in range(N)]
            # 1. 시계방향으로 90도 회전시키기
            for r in range(N):
                for c in range(N):
                    turn_board[c][N - 1 - r] = test_board[r][c]
            # 2. 오른쪽으로 밀기
            rightBlock(turn_board)
            # 시계 방향으로 회전시킨 것을 270도 회전하여 원상태로 만들기
            for r2 in range(N):
                for c2 in range(N):
                    test_board[N - 1 - c2][r2] = turn_board[r2][c2]

        else: # 아래로 미는 경우 (시계방향으로 90도 회전시키고 왼쪽으로 밀기)
            turn_board = [[0] * N for _ in range(N)]
            # 1. 시계방향으로 90도 회전시키기
            for r in range(N):
                for c in range(N):
                    turn_board[c][N - 1 - r] = test_board[r][c]
            # 2. 오른쪽으로 밀기
            leftBlock(turn_board)
            # 시계 방향으로 회전시킨 것을 270도 회전하여 원상태로 만들기
            for r2 in range(N):
                for c2 in range(N):
                    test_board[N - 1 - c2][r2] = turn_board[r2][c2]

    # 가장 큰 블록이 있는지 탐색하기
    for n in range(N):
        max_block = max(max_block, max(test_board[n]))

print(max_block)

참고) 반례 예시

1
2
3
4
5
6
7
8

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

# 출력: 64
Solve coding problems, baekjoon
baekjoon python
This post is licensed under CC BY 4.0 by the author.
Recent Update
Contents

[Database] SQL - SELECT문 정복하기 (MySQL)

[programmers] SQL 고득점 Kit - SELECT 문제 답모음 (MySQL)

Comments powered by Disqus.