[백준 12100번] 2048(Easy) (파이썬)

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

12100번: 2048 (Easy)

easy하다는 문제명과 달리

그렇지 못한 문제.

 

이 문제는 DFS로 접근합니다.

상하좌우로 움직이는 경우가 있고

각각을 총 5번 움직이면

최대를 구합니다.

https://door-of-tabris.tistory.com/entry/%EB%B0%B1%EC%A4%80-15683%EB%B2%88-%EA%B0%90%EC%8B%9C%ED%8C%8C%EC%9D%B4%EC%8D%AC-1

[백준 15683번] 감시(파이썬)

이 문제에서 DFS와 백트레킹

2가지에 대해서 보고오셔도 좋습니다.

 

사실, 코테를 많이 푸시는 분들이라면

이거는 금방 생각하기 쉽습니다.

문제는 이동하는 방법...

 

if d == 0:  # 오른쪽으로 이동할 때
    com = [[0] * N for _ in range(N)]
    for x in range(N):
        for y in range(N - 2, -1, -1):
            if room[x][y] > 0:
                now_y = y
                now = room[x][y]
                # 범위를 벗어나지 않거나, 또다른 숫자를 만나기 전까지 이동
                while now_y + dy[d] < N:
                    now_y += dy[d]
                    if not room[x][now_y] == 0:
                        now_y -= dy[d]
                        break

                if now_y + dy[d] == N:
                    room[x][y] = 0
                    room[x][now_y] = now

                else:
                    if room[x][now_y + dy[d]] == now and not com[x][now_y + dy[d]]:
                        # 이동해서 마주친게  지금것과 같은데, 이전에 더하지 않음
                        room[x][y] = 0
                        room[x][now_y + dy[d]] = now * 2
                        com[x][now_y + dy[d]] = 1

                    else:
                        # 이동한거랑 마주치는 게 같지 않거나, 이전에 더했다면
                        room[x][y] = 0
                        room[x][now_y] = now

 

 

제가 했던 방식입니다.

오른쪽으로 이동할 때의 케이스만 가져와봤습니다.

저는 com이라는 별도의 리스트를 만들어서

이동 중 합쳐진 건 다시 합쳐지지 않게 만들었습니다.

오른쪽으로 이동하는 것이니

맨 오른쪽부터 이동시켜줍니다.

(문제에서 조건을 보면, 

이동하는 영역을 우선적으로 합치라고 되어있습니다.)

리스트를 쭉 보다가

0이 아닌 요소를 발견하면 이동을 시도합니다.

그 요소를 중심으로

(오른쪽이니깐 y값이 이동)

계속 이동해줍니다.

이동하다가 같은 값을 만나면 *2

아니라면 서로 순서 바꾸기

이런식으로 구현했습니다.

 

논리적으로는 맞았던 것 같았는데

이 방식으로 제출하니

최대 14%에서 틀렸습니다가 떴습니다.

범위도 수정하고 별짓 다했는데

여전히 틀렸다고 떴습니다.

뭔지는 잘 모르지만

아마 합쳐질 때를 구현하는

com리스트를 쓰는 방식에서

에러가 있었던 것 같습니다.

 

이렇게 한참 고민하다가

결국 구글링으로 풀이참조를 했습니다.

 

오른쪽으로 가는 케이스에 대한 예시입니다.

pointer라는 변수를 사용하면서

'오른쪽으로 하나씩 밀어가는'

느낌으로 이동을 시키는 방법입니다.

 

# 백준 12100번 2048(Easy)

from copy import deepcopy

N = int(input())

room = [list(map(int, input().split())) for _ in range(N)]

max_num = 0

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def dfs(depth):
    global max_num
    global room

    # 최대 5번 이동했으면 그 때 가장 큰 걸 받는다
    if depth == 5:
        maxin = 0
        for x in range(N):
            for y in range(N):
                if room[x][y] > 0:
                    maxin = max(maxin, room[x][y])
        max_num = max(max_num, maxin)

        return

    temp_a = deepcopy(room)
    for d in range(4):

        if d == 0:  # 오른쪽으로 이동할 때
            for x in range(N):
                pointer = N - 1
                for y in range(N - 2, -1, -1):
                    if room[x][y] > 0:
                        now = room[x][y]
                        room[x][y] = 0
                        if room[x][pointer] == 0:
                            room[x][pointer] = now
                        elif room[x][pointer] == now:
                            room[x][pointer] *= 2
                            pointer -= 1
                        else:
                            pointer -= 1
                            room[x][pointer] = now
        elif d == 1:  # 왼쪽으로 이동할 때
            for x in range(N):
                pointer = 0
                for y in range(1, N):
                    if room[x][y] > 0:
                        now = room[x][y]
                        room[x][y] = 0
                        if room[x][pointer] == 0:
                            room[x][pointer] = now
                        elif room[x][pointer] == now:
                            room[x][pointer] *= 2
                            pointer += 1
                        else:
                            pointer += 1
                            room[x][pointer] = now
        elif d == 2:  # 위로 이동할 때
            for y in range(N):
                pointer = 0
                for x in range(1, N):
                    if room[x][y] > 0:
                        now = room[x][y]
                        room[x][y] = 0
                        if room[pointer][y] == 0:
                            room[pointer][y] = now
                        elif room[pointer][y] == now:
                            room[pointer][y] *= 2
                            pointer += 1
                        else:
                            pointer += 1
                            room[pointer][y] = now
        elif d == 3:  # 아래로 이동할 떄
            for y in range(N):
                pointer = N - 1
                for x in range(N - 2, -1, -1):
                    if room[x][y] > 0:
                        now = room[x][y]
                        room[x][y] = 0
                        if room[pointer][y] == 0:
                            room[pointer][y] = now
                        elif room[pointer][y] == now:
                            room[pointer][y] *= 2
                            pointer -= 1
                        else:
                            pointer -= 1
                            room[pointer][y] = now
        # print('dfs')
        # road.append(d)
        # map_tmp.append(room)
        # print(road)
        dfs(depth + 1)
        room = deepcopy(temp_a)
        # road.pop()
        # map_tmp.pop()


dfs(0)
print(max_num)

https://chldkato.tistory.com/163

백준 12100 2048 (Easy) (파이썬)

https://cijbest.tistory.com/86

[백준 12100 : PYTHON] 2048 (Easy)

제가 참고한 풀이입니다.

 

결과만 보면 간단해보이지만

실제로는 엄청한 고민이 필요했습니다.

후...이제 ekrclrh 외워야지...