글 읽기 - 파이썬 시간 초과

bogsoony12 2년 전 1

왜 시간초과가 날까요? 시간초과가 나는데 그 원인을 잘 모르겠습니다. 18% 정도에서 나는데 도와주세요ㅠㅠ

R, C = map(int, input().split())
board = []
for i in range(R):
    w = []
    for st in input():
        w.append(st)
    board.append(w)

gmax = 1
code = {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4, 'F': 5, 'G': 6, 'H': 7, 'I': 8, 'J': 9, 'K': 10, 'L': 11, 'M': 12, 'N': 13, 'O': 14, 'P': 15, 'Q': 16, 'R': 17, 'S': 18, 'T': 19, 'U': 20, 'V': 21, 'W': 22, 'X': 23, 'Y': 24, 'Z': 25}

def sol(loc, unit_max, checklist):
    global gmax
    return_time = 0
    x, y = loc[0], loc[1]
    check_x = [[x-1>=0, x-1], [x+1<=R-1, x+1]]
    check_y = [[y-1>=0, y-1], [y+1<=C-1, y+1]]
    for i in range(2):
        for j in range(2):
            if i == 0:
                if check_x[j][0]:
                    new_x = check_x[j][1]
                    if checklist[code[board[new_x][y]]] == False:
                        checklist[code[board[new_x][y]]] = True
                        sol([new_x, y], unit_max + 1, checklist)
                        checklist[code[board[new_x][y]]] = False
                        return_time += 1
            elif i == 1:
                if check_y[j][0]:
                    new_y = check_y[j][1]
                    if checklist[code[board[x][new_y]]] == False:
                        checklist[code[board[x][new_y]]] = True
                        sol([x, new_y], unit_max + 1, checklist)
                        checklist[code[board[x][new_y]]] = False     
                        return_time += 1       
    if return_time == 0:
        gmax = max(gmax, unit_max)
        if unit_max == 26:
            print(checklist)
        return
c = [False for _ in range(26)]
c[code[board[0][0]]] = True
sol([0, 0], 1, c)
print(gmax)

bogsoony2 2년 전 1

혹시 반례 찾아보셨나요? ㅎㅎ

guswns137 2년 전 1

딕셔너리 사용 시 시간 복잡도가

best는 O(1)

wast O(N)

이라 시간이 많이 소요될 수 있습니다.

hongii2 1년 전 0

이거 비트필드를 이용한 다이나믹 프로그래밍으로 풀 수 있나요?

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

문제

문제

출처

ICPC

파이썬 시간 초과

bogsoony12 2년 전 1

bogsoony2 2년 전 1

guswns137 2년 전 1

hongii2 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말