SHISENSHO 시간초과 관련 문의 드립니다.

  • memorys
    memorys

    안녕하세요 사청성 문제 관련 문의 드립니다.
    SHISENSHO
    https://algospot.com/judge/problem/read/SHISENSHO

    아래 코드를 보시면 아시겠지만...
    많이 지저분 합니다..ㅠㅠ
    아직 파이썬의 능력을 끌어내기에는 역부족인듯합니다...
    이 복잡한 코드를 간략히 우선 설명드리자면

    테스트코드를 포함하고있습니다.
    재귀함수 형태로 구현하였습니다.

    1. 입력된 보드에서 행 또는 열이 모두 공백인 경우 해당 영역을 삭제합니다. (입력에따라서는 불필요 또는 안하니만 못한 상황이 발생할 수 있습니다)
    2. 해당 보드의 모든 칸에 대하여 가능성을 판단합니다.

      2.1 3번 이상 꺽였거나, 보드를 벗어낫을 때 재귀 종료
      2.2 공백이 아닌칸에 도달하였을 때 답을 체크하거나 종료
      2.3 더 뻗어나가야할 경우 상하좌우로 재귀함수 호출

      2.3.1 뒤로 가지는 못함
      2.3.2 방향이 전환되었을 경우 코스변경카운트를 증가
    3. 2.2에서 답을 체크할때마다 결과값을 증가시키며, 해당 결과를 출력

    이상입니다.
    짝을 찾아내는 수학적(?) 알고리즘을 따로 생각해내지 못하여 탐색토록 하였습니다.
    해당 문제는 오답이 아닌 시간초과인 관계로... 알고리즘 자체가 글러먹은 녀석일 수 있습니다..ㅠㅠ
    랜덤으로 돌려보아도 작은 케이스가 아니고서는 답을 정확히 판단할 수가 없어서 큰 케이스는 결과가 나오는 것만 확인하였습니다.
    채점에서 어떤 입력을 사용하는지는 알 수 없으나 5초라는 시간이 다 소비될만큼 길게 돌아가지는 않는 녀석으로 보입니다 ㅠㅠ
    혹시 이 상황을 보고 '이게 문제네!!' 하고 딱 떠오르시거나 문제가 될만한 input 을 알고계신다면 답변 부탁드립니다
    감사합니다!

    코드 블럭

    import random
    
    def printBoard():
        print ''
        for i in board:
            print reduce(lambda x, y: x + y, i)
        print ''
    
    def findRemovablePair(nextX, nextY, startX, startY, curveCount, lastDirection):
        global findCount
        if curveCount > 3:
            return
        if nextX < 0 or nextX > board[0].__len__() - 1 or nextY < 0 or nextY > board.__len__() - 1:
            return
        if board[nextY][nextX] == board[startY][startX] and lastDirection != 0:
            if (nextY, nextX, startY, startX) in findList or (startY, startX, nextY, nextX) in findList:
                return
            else:
                findList.append((nextY, nextX, startY, startX))
                findCount += 1
                return
        if board[nextY][nextX] != '.' and lastDirection != 0:
            return
    
        if lastDirection != 2:
            findRemovablePair(nextX+1, nextY, startX, startY, lastDirection == 1 and curveCount or curveCount + 1, 1)
        if lastDirection != 1:
            findRemovablePair(nextX-1, nextY, startX, startY, lastDirection == 2 and curveCount or curveCount + 1, 2)
        if lastDirection != 4:
            findRemovablePair(nextX, nextY+1, startX, startY, lastDirection == 3 and curveCount or curveCount + 1, 3)
        if lastDirection != 3:
            findRemovablePair(nextX, nextY-1, startX, startY, lastDirection == 4 and curveCount or curveCount + 1, 4)
    
    def refreshBoard(target):
        if target.__len__() < 1:
            return
        for i in reversed(range(target.__len__())):
            if filter(lambda x: x != '.', target[i]).__len__() == 0:
                del target[i]
        for i in reversed(range(target[0].__len__())):
            count = 0
            for j in range(target.__len__()):
                if target[j][i] != '.':
                    break
                count += 1
                if count == target.__len__():
                    for k in range(target.__len__()):
                        del target[k][i]
        for i in range(board.__len__()):
            board[i].insert(0, '.')
            board[i].append('.')
        board.insert(0, ['.' for col in range(board[0].__len__())])
        board.append(['.' for col in range(board[0].__len__())])
    
    for lll in range(input()):
    #for lll in range(100):
        global board
        global findCount
        global findList
    
    
        if 1==2:
            boardSize = [random.randrange(3,51), random.randrange(3,51)]
            board = [['.' for col in range(boardSize[1])] for row in range(boardSize[0])]
            for i in range(boardSize[0]):
                for j in range(boardSize[1]):
                    temp = random.randrange(97, 117)
                    if temp < 107:
                        board[i][j] = chr(temp)
        else:
            boardSize = map(lambda x: int(x), raw_input().split())
            board = [['.' for col in range(boardSize[1])] for row in range(boardSize[0])]
            for i in range(boardSize[0]):
                inputBoard = raw_input()
                for j in range(inputBoard.__len__()):
                    if inputBoard[j] != '.':
                        board[i][j] = inputBoard[j]
        refreshBoard(board)
        findCount = 0
        findList = []
        for i in range(board.__len__())[1:board.__len__()]:
            for j in range(board[0].__len__())[1:board[0].__len__()]:
                if board[i][j] != '.':
                    findRemovablePair(j, i, j, i, 0, 0)
        print findCount
    }
    

    파이썬 2.7에 파이참사용하였습니다


    7년 전
4개의 댓글이 있습니다.
  • JongMan
    JongMan

    시간 초과 문제는 한 번 방문한 상태 (a위치에서 b위치까지 c번 꺾어서 왔고 현재 방향은 d) 를 두 번 이상 방문하지 않게 하면 어렵잖게 해결할 수 있을거 같네요.

    파이썬 쓰시니 반가워서 스타일 고치실 만한 점 몇 개 리플로 답니다 ㅎㅎ

    1. x.__len__() 대신 len(x)
    2. reversed(range(n)) 대신 range(n, -1, -1)
    3. len(filter(lambda x: .., a)) == 0 대신 all(x == '.' for x in a)

    7년 전 link
  • memorys
    memorys

    2번꺽는 것(직선3개)으로는 평행선으로는 가능하나 원위치로 올 수가 없어서 (ㄷ 형태이기때문에) 제자리로 오지 않을거라 판단하고 있습니다 ㅠ
    새로운 언어 공부할 겸 알고리즘문제로 머리도 써볼겸 둘을 접목해서 파이썬으로 알고스팟을 뚫고있어요 ㅋ 원래 C 쪽이었는데 다른 코드들 퍼포먼스를 보면 막 C 로 하고싶어지네요
    하지만 파이선 공부가 목적이니 끝까지 파이썬으로 ㅋㅋ
    파이썬으로 한바퀴 돌고나면 Go를 써볼까 합니다
    조언주신 부분은 적극 참고하도록 하겠습니다
    감사해요!!


    7년 전 link
  • JongMan
    JongMan

    제자리에 오는 문제가 아니라, 한 상태에 두 가지 방법 이상으로 도달할 수 있는 경우들을 다 시도하고 계신 것 같아서요. 그 때문에 시간 제한에 걸리는 게 아닌가 합니다.


    7년 전 link
  • memorys
    memorys

    아.. 그 내용은 맞습니다 ㅠ 시작,종료를 주고 길을 찾는게 아니라 주변을 탐색해 나가는 것이다 보니 돌다보면 같은 종료점을 몇가지 루트가 반복하게 됩니다..
    알고리즘 자체를 바꿔봐야겠네요


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.