글 읽기 - 시간 초과를 어떻게 해결하면 좋을지 모르겠습니다. 도와주세요

shhmun02 1년 전 0

dfs와 백트래킹 방법으로 풀었는데 어느 부분을 줄여야 시간초과를 줄일 수 있는지 모르겠습니다.

from sys import stdin
input = stdin.readline

r, c = map(int, input().split())
arr = [ list(input().strip()) for _ in range(r) ]


def dfs(start_r,start_c, cnt):
    global answer
    answer = max(answer, cnt)
    res.append(arr[start_r][start_c])
    moving = [[1,0],[0,1],[-1,0],[0,-1]]
    for ro, cr in moving: # 4 방향을 확인
        spot_r = start_r + ro
        spot_c = start_c + cr
        if spot_r > -1 and spot_r < r and spot_c > -1 and spot_c < c:
            if not arr[spot_r][spot_c] in res:
                dfs(spot_r, spot_c, cnt + 1)
                res.pop() 
    
answer = 0
res = []
spot = []
dfs(0,0,1)
print(answer)

hsw0194 1년 전 2

17행에서 res는 list인데 `in` 연산자의 시간복잡도를 확인해보시겠어요?

shhmun02 1년 전 0

감사합니다 !!

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

문제

문제

출처

ICPC

시간 초과를 어떻게 해결하면 좋을지 모르겠습니다. 도와주세요

shhmun02 1년 전 0

hsw0194 1년 전 2

shhmun02 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말