글 읽기 - 이문제는 도대체 어떻게 해야 시간초과가 안뜰까요

dlehrud451 2년 전 0

진짜 뭘 어떻게 해야 시간초과가 안뜨는지 너무 궁금합니다. 이거 풀다가 이십대에 고혈압 올것같아요;

def dfs(r,c,total):
    global maximum
    maximum=max(maximum,total)
    for i in range(4):
        nr=r+dr[i]
        nc=c+dc[i]
        if 0<=nr<n and 0<=nc<m:
            if graph[nr][nc] not in s:
                s.add(graph[nr][nc])
                dfs(nr,nc,total+1)
                s.remove(graph[nr][nc])


n,m=map(int,input().split())
graph=[list(input()) for _ in range(n)]

maximum=0
s=set()
s.add(graph[0][0])

dr=[0,-1,0,1]
dc=[1,0,-1,0]
dfs(0,0,1)

print(maximum)

yukariko 2년 전 1

풀이는 문제가 없어보입니다만 파이썬 코드가 느려서 시간초과가 나는것 같습니다.

다른 언어를 사용하시거나 파이썬에서 할 수 있는 최적화를 시도해보세요.

또는 pypy 로 제출해보는것도 방법입니다.

muzigae 2년 전 2

set을 만들어서 이전 알파벳이 나왔는지 확인하는 방법이 느려서 시간 초과가 나는 듯하네요.

알파벳에 해당하는 길이 26의 배열을 만들어서 true, false 이런 식으로 관리해주면 빠를 겁니다.

dlehrud451 2년 전 0

muzigae 님 감사합니다 set이 속도가 더 빠르다고 생각해서 저렇게 짰는데 list가 더 빨랐습니다. 덕분에 문제 해결했습니다. 감사합니다!

hhkim593 1년 전 0

muzigae 님 감사합니다. 알파벳 체크 방식으로 For문을 돌려서 시간초과 떴었는데

말씀하신 리스트로 복잡도를 해소시켜 풀었습니다! 참고가 되었습니다 ㅎㅎ

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

문제

문제

출처

ICPC

이문제는 도대체 어떻게 해야 시간초과가 안뜰까요

dlehrud451 2년 전 0

yukariko 2년 전 1

muzigae 2년 전 2

dlehrud451 2년 전 0

muzigae 님 감사합니다 set이 속도가 더 빠르다고 생각해서 저렇게 짰는데 list가 더 빨랐습니다. 덕분에 문제 해결했습니다. 감사합니다!

hhkim593 1년 전 0

muzigae 님 감사합니다. 알파벳 체크 방식으로 For문을 돌려서 시간초과 떴었는데

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말