2048(Easy) [SW 역량 테스트 기출 문제]

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

12100번: 2048 (Easy)

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

89429

26268

15452

26.497%

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

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

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

문제 해결

해당 문제는 백트랙킹을 이용하여 최대 점수를 얻는 경우의 수를 찾는 시물레이션 문제이다. 해당 문제는 총 4방향을 5번안에 탐색을 해야 하므로 4^5의 시간복잡도 그리고 모든 보드판을 다 움직여야 하므로 최대 4^5 * 20 *20의 시간복잡도로 해결이 가능한 문제이다.

 

총 3번의 트라이 끝에 해결했다. 시물레이션 문제는 아래와 같은 프로세스를 따르면서 하는게 도중에 길을 잃지 않는 방법인것 같다...

1. 로직 구성

2. 수도 코드 작성

3. 각 스텝에 맞게 구현

 

위 프로세스를 따르면서 해당 문제에서 주어진 특별한 조건들을 잘 구현해야 한다. 가장 신경써야 하는 부분은 아래와 같다고 생각했다.

1. 구슬 탈출2와 마찬가지로 한쪽으로 쭉 밀려가야함

2. 밀려가는 도중 자신과 같은 점수를 만나면 합쳐야 함

3. 만약 점수가 같더라도 1회 이동에서 합쳐진 적이 있다면 합칠 수 없음

 

위와 같은 로직을 수행하기 위해서 나는 C++ 구조체를 선언했던 버릇이 있어서 mydata()라는 점수와 합쳐진 적이 있는지 체크하는 2개의 멤버 변수를 가진 클래스를 선언했다. 이제 아주 간단한 아래 구조체를 이용해서 문제를 풀어 나갔다.

class myData():
    score = 0
    isSum = False
    
    def __init__(self, score):
        self.score = int(score)

 

 

1. 4방향 탐색 

백트랙킹의 기본적인 루트 부분에서부터 탐색을 하는 기본적인 for문을 작성하고 FindMaxScore 함수를 통해 실제 백트랙킹 주요 로직을 구현했다.

for dir in direction:
    myBoard = grid
    findMaxScore(dir, 1, myBoard)

 

2. 백트랙킹 로직

def findMaxScore(dir, turn, board):
    if turn > 5:
        answerList.append(findMax(board))
        return
    
    #-- 4방향 처리
    newBoard = copy.deepcopy(board)
    
    if dir =="U":
        newBoard = moveup(newBoard)
    elif dir =="D":
        newBoard = movedown(newBoard)
    elif dir =="L":
        newBoard = moveleft(newBoard)
    elif dir =="R":
        newBoard = moveright(newBoard)
    
    for dir in direction:
        findMaxScore(dir, turn+1, newBoard)

- 주어진 이동횟수는 5이므로 그 이상이 되는 순간 최댓값을 계산

- 이동 횟수가 남아있다면 깊은 복사를 통해 보드에 대한 정보를 옮김

- 각각 방향에 맞게 로직 처리

 

3. 주요 이동 로직

가장 핵심적인 로직이고 up 하나를 구현해서 나머지는 방향만 수정하는 방식으로 처리했다.

def reset(board):
    for i in range(N):
        for j in range(N):
            board[i][j].isSum = False
    return board
def moveup(OldBoard):
    newBoard = OldBoard
    dir = -1
    for y in range(N):
        for x in range(N):
            target = newBoard[y][x].score
            if target == 0:
                continue
            ny = y + dir
            while 0 <= ny < N: #--  범위 체크
                #-- 1. 이동할 수 있는 0이 있는 공간
                if newBoard[ny][x].score == 0:
                    newBoard[ny][x] = newBoard[ny-dir][x] #-- 이전 데이터 가져오고 삭제
                    newBoard[ny-dir][x] = myData(0)
                    ny += dir
                #-- 2. 나랑 같은 숫자
                elif newBoard[ny][x].score == target:
                    #-- -> 같은 숫자이지만 이미 합쳐진 경우
                    if newBoard[ny][x].isSum == True:
                        break
                    #-- -> 같은 숫자이고 처음 합쳐진 경우
                    else:
                        newBoard[ny][x].score *=2
                        newBoard[ny][x].isSum = True
                        newBoard[ny-dir][x] = myData(0)
                        break
                    
                #-- 3. 이동할 수 없는 다른 숫자
                else:
                    break
    return reset(newBoard)

로직은 매우 직관적이다.

- 보드를 순회하면서 target을 저장하고 해당 점수블록이 이동이 가능하다면 아래 조건에 따라 움직인다.

- 이동하는 공간이 0이라면 -> 바로 이동하고 또 다른 가능성 탐색

- 이동하는 공간이 나와 같은 숫자라면 

    - 같은 숫자이지만 이미 합쳐진 경우 : 멈춤

    - 같은 숫자이고 합쳐진 적이 없다면 : 합쳐짐

- 다른 숫자라면 -> 멈춤

 

위 이동 로직이 끝나고 나서 이미 합쳐진 경우에 대한 True False 값은 다음에 초기화 되야 하므로 reset 함수를 통해 초기화 시켜줬다.

 

위와 비슷한 방식으로 4방향 구현을 끝내고 제출한 결과 3트만에 성공했다 ! 쉽지 않다!!! 그래도 이전 구슬탈출2를 해본 경험 덕분에 중력 구현 비슷한 부분은 쉽게 해결할 수 있었다!! 주륵...