글 읽기 - 시간줄일 수 있는 부분 봐주세요

kimyj90 5년 전 0

일단 대회 테스트케이스는 다 맞았는데요 시간초과가 납니다.

import sys
import copy

# global
dx = [-1,0,0,1]
dy = [0,-1,1,0]

class Solution:

    def __init__(self):
        self.board = []
        self.ret = 0
        self.row = 0
        self.col = 0

    def input(self):
        r_c = sys.stdin.readline().split(" ")
        r_c = [int(r_c[i].replace("\n",'')) if i==1 and '\n' in r_c[i] else int(r_c[i]) for i in range(0,2)]
        self.board = [input() for i in range(0,r_c[0])]
        self.row = len(self.board)
        self.col = len(self.board[0])

    def sol(self):
        lst=[]
        self.recursive_call(0,0,lst)

        return self.ret


    def recursive_call(self,x,y,lst):
        lst.append(self.board[y][x])

        for i in range(0,4):
            newX = x+dx[i]
            newY = y+dy[i]
            if newX >=0 and newY >=0:
                if newX < self.col and newY < self.row:
                    if self.board[newY][newX] not in lst:
                        # 여기서 새롭게 리스트를 만들어줍니다. 파이썬의 경우 함수안에 들어갔다가 온 리스트가 업데이트는 되는 call by ref의 특성을 가지고 있습니다.
                        # 여기서 느려지는것 같은데 어떻게 바꿔줘야 할지모르겠습니다.
                        newlst = self.newlist(lst)
                        self.recursive_call(newX,newY,newlst)
                    if len(lst) > self.ret:
                        self.ret = len(lst)


    def newlist(self,lst):
        retlst = [lst[i] for i in range(0,len(lst))]
        return retlst

if __name__ == "__main__":
    s = Solution()
    s.input()
    out = s.sol()
    print(out)

seico75 5년 전 0

newlst = self.newlist(lst) 는 newlst = lst.copy() 로 대체가능할 것 같습니다.

하지만 더 좋은 것은 그냥 lst 넘기고

45 라인에 31라인과 같이 indent 맞춰서 lst.remove(self.board[y][x]) 하는 것이 더 나을 것도 같습니다.

근데..

이거 다해도 시간초과는 나네요.

kimyj90 5년 전 0

음 일단 감사합니다

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

문제

문제

출처

ICPC

시간줄일 수 있는 부분 봐주세요

kimyj90 5년 전 0

seico75 5년 전 0

kimyj90 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말