글 읽기 - (dfs) 파이썬 혹시 반례가 있을까요?

onlyou0416 3년 전 0

시작하자마자 틀리는데,

어떤 부분을 놓치고 있는지 잘 모르겠네요..!

import copy 

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

def move(t,board) -> int:#return maximum 
    # type 1: up, 2: right, 3: down, 4: left
    if t==1:
        for i in range(N): #when column==i
            # 1. save only none-zero values in q
            q = []
            for j in range(N):
                if board[j][i]!=0:
                    q.append(board[j][i])
            
            # 2. merge the same values
            idx = 0
            while q:
                if len(q)>=2:
                    if q[0]==q[1]:
                        board[idx][i] = q[0]*2
                        q.pop(0)
                    else: board[idx][i] = q[0]
                    q.pop(0)
                else: board[idx][i] = q.pop(0)
                idx+=1
            for k in range(idx,N):
                board[k][i] = 0
    elif t==3:
        for i in range(N):
            q = []
            for j in range(N):
                if board[j][i]!=0:
                    q.append(board[j][i])
            idx = N-1
            while q:
                if len(q)>=2:
                    if q[-1]==q[-2]:
                        board[idx][i] = q[-1]*2
                        q.pop()
                    else: board[idx][i] = q[-1]
                    q.pop()
                else: board[idx][i] = q.pop()
                idx-=1
            for k in range(idx+1):
                board[k][i] = 0
    elif t==2:
        for i in range(N):
            q = []
            for j in range(N):
                if board[i][j]!=0:
                    q.append(board[i][j])
            idx = N-1
            while q:
                if len(q)>=2:
                    if q[-1]==q[-2]:
                        board[i][idx] = q[-1]*2
                        q.pop()
                    else: board[i][idx] = q[-1]
                    q.pop()
                else: board[i][idx] = q.pop()
                idx-=1
            for k in range(idx+1):
                board[i][k] = 0
    else:
        for i in range(N):
            q = []
            for j in range(N):
                if board[i][j]!=0:
                    q.append(board[i][j])
            idx = 0
            while q:
                if len(q)>=2:
                    if q[0]==q[1]:
                        board[i][idx] = q[0]*2
                        q.pop(0)
                    else: board[i][idx] = q[0]
                    q.pop(0)
                else:board[i][idx] = q.pop(0)
                idx+=1
            for k in range(idx,N):
                board[i][k] = 0
    return board

ans = 0
def dfs(t,cnt,board):
    
    p_board = copy.deepcopy(board)
    board = move(t,board)
    cnt+=1

    if cnt==5:
        global ans
        ans = max(max(max(board[i] for i in range(N))), ans)
        return

    copy_boards = [copy.deepcopy(board) for _ in range(4)]
    for i in range(1,5):
        if i is not t: dfs(i,cnt,copy_boards[i-1])
    
    board = p_board

boards = [copy.deepcopy(board) for _ in range(4)]
for t in range(4):
    dfs(t+1,0,boards[t])

print(ans)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(dfs) 파이썬 혹시 반례가 있을까요?

onlyou0416 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말