[파이썬 python] 백준 - 12100 2048(easy)

2048 (Easy) 성공

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 시뮬레이션
• 백트래킹

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

12100번: 2048 (Easy)

 

---

answer = 0
N = int(input())
board = [[0 for y in range(N)] for x in range(N)]
for x in range(N):
        board[x] = list(map(int,input().split()))
visited = [[0 for y in range(N)] for x in range(N)]

def up(next_b):
        for x in range(len(visited)):
                for y in range(len(visited)):
                        visited[x][y] = 0

        for x in range(1, len(next_b)):
                for y in range(len(next_b)):
                        tmp_x, tmp_y = x, y
                        while True:
                                if next_b[tmp_x-1][tmp_y] == 0:
                                        next_b[tmp_x-1][tmp_y] = next_b[tmp_x][tmp_y]
                                        next_b[tmp_x][tmp_y] = 0
                                        tmp_x -= 1
                                        if tmp_x <= 0:
                                                break
                                elif next_b[tmp_x-1][tmp_y] == next_b[tmp_x][tmp_y] and visited[tmp_x-1][tmp_y] == 0:
                                        next_b[tmp_x-1][tmp_y] *= 2
                                        next_b[tmp_x][tmp_y] = 0
                                        visited[tmp_x-1][tmp_y] = 1
                                        break
                                else:
                                        break
        return next_b

def down(next_b):
        for x in range(len(visited)):
                for y in range(len(visited)):
                        visited[x][y] = 0

        for x in range(len(next_b)-2, -1, -1):
                for y in range(len(next_b)):
                        tmp_x, tmp_y = x, y
                        while True:
                                if next_b[tmp_x+1][tmp_y] == 0:
                                        next_b[tmp_x+1][tmp_y] = next_b[tmp_x][tmp_y]
                                        next_b[tmp_x][tmp_y] = 0
                                        tmp_x += 1
                                        if tmp_x >= len(next_b)-1:
                                                break
                                elif next_b[tmp_x+1][tmp_y] == next_b[tmp_x][tmp_y] and visited[tmp_x+1][tmp_y] == 0:
                                        next_b[tmp_x+1][tmp_y] *= 2
                                        next_b[tmp_x][tmp_y] = 0
                                        visited[tmp_x+1][tmp_y] = 1
                                        break
                                else:
                                        break
        return next_b

def left(next_b):
        for x in range(len(visited)):
                for y in range(len(visited)):
                        visited[x][y] = 0

        for y in range(1, len(next_b)):
                for x in range(0, len(next_b)):
                        tmp_x, tmp_y = x, y
                        while True:
                                if next_b[tmp_x][tmp_y-1] == 0:
                                        next_b[tmp_x][tmp_y-1] = next_b[tmp_x][tmp_y]
                                        next_b[tmp_x][tmp_y] = 0
                                        tmp_y -= 1
                                        if tmp_y <= 0:
                                                break
                                elif next_b[tmp_x][tmp_y-1] == next_b[tmp_x][tmp_y] and visited[tmp_x][tmp_y-1] == 0:
                                        next_b[tmp_x][tmp_y-1] *= 2
                                        next_b[tmp_x][tmp_y] = 0
                                        visited[tmp_x][tmp_y-1] = 1
                                        break
                                else:
                                        break
        return next_b

def right(next_b):
        for x in range(len(visited)):
                for y in range(len(visited)):
                        visited[x][y] = 0

        for y in range(len(next_b)-2, -1, -1):
                for x in range(0, len(next_b)):
                        tmp_x, tmp_y = x, y
                        while True:
                                if next_b[tmp_x][tmp_y+1] == 0:
                                        next_b[tmp_x][tmp_y+1] = next_b[tmp_x][tmp_y]
                                        next_b[tmp_x][tmp_y] = 0
                                        tmp_y += 1
                                        if tmp_y >= len(next_b)-1:
                                                break
                                elif next_b[tmp_x][tmp_y+1] == next_b[tmp_x][tmp_y] and visited[tmp_x][tmp_y+1] == 0:
                                        next_b[tmp_x][tmp_y+1] *= 2
                                        next_b[tmp_x][tmp_y] = 0
                                        visited[tmp_x][tmp_y+1] = 1
                                        break
                                else:
                                        break
        return next_b

def new_b(b):
        new_b = [[0 for y in range(len(b))] for x in range(len(b))]
        for x in range(len(b)):
                for y in range(len(b)):
                        new_b[x][y] = b[x][y]
        return new_b

def dfs(b, cnt):
        global answer
        if cnt == 5:
                for x in range(len(b)):
                        answer = max(answer, max(b[x]))
                return

        for x in range(len(b)):
                answer = max(answer, max(b[x]))

        cnt += 1
        dfs(up(new_b(b)), cnt)
        dfs(down(new_b(b)), cnt)
        dfs(left(new_b(b)), cnt)
        dfs(right(new_b(b)), cnt)

def solution():
        global answer
        dfs(board, 0)
        print(answer)

solution()

 

후기

 샘숭 기출문제 문제집에 있어서 풀었다. 원래는 이런 구현 문제들을  빠른 시간 안에 풀어야한다고 하지만 시간이 좀 걸렸다.(문제 조조건 중에, 한번 합친것은 한 과정에서는 다시 합칠 수 없다 를 잘 못봐서 출력이 이상해졌다) 문제의 조건들과 제한사항들을 잘 이해하고, 재빠른 복붙이 답이다.

 

풀이

 * (재빠른 복사 붙여넣기가 핵심적이다)

 * 주의) 2차원 배열을 깊은 복사로 얕은 복사는 xx

 * 상하좌우를 DFS로 5번씩 돌아서 모든 경우의 수를 찾는다.

 

(1) DFS를 시작한다. DFS 인자로 보드(2차원 배열)을 받는다. 이것을 상하좌우로 각각 1번씩 이동시키고 cnt += 1

(2) 상하좌우로 이동한다. 이동할 곳이 0이라면, 계속 이동시킨다(board 범위 밖이라면 break). 이동할 곳이 자신과 같다면, 자기자신과 이동시킬 곳을 합쳐주고 break. 그 밖이라면 그냥 break. 이동시키는 것에서 주의할 점은, 한 번 합친 것은 한 과정에서는 다시 합칠 수 없다는 것이다. 이것을 위해서 visited를 사용하였고, 한번 합친 블록은 방문했다는 것을 표시하여 다시 방문하지 않도록 했다.(visited은 사용할 떄 미리 초기화)

(3) cnt 가 5번이 되었다면 DFS를 리턴한다.