algospot.com :: 질문과 답변: SHISENSHO 시간초과 관련 문의 드립니다.

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

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

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

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

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

2.1 3번 이상 꺽였거나, 보드를 벗어낫을 때 재귀 종료
2.2 공백이 아닌칸에 도달하였을 때 답을 체크하거나 종료
2.3 더 뻗어나가야할 경우 상하좌우로 재귀함수 호출
```
2.3.1 뒤로 가지는 못함
2.3.2 방향이 전환되었을 경우 코스변경카운트를 증가
```
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
시간 초과 문제는 한 번 방문한 상태 (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

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

7년 전 link
JongMan

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

7년 전 link
memorys

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

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

JongMan

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

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

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

7년 전 link

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

7년 전 link

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

7년 전 link

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

7년 전 link

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

SINCE 2007

다가오는 이벤트들

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

코드 블럭

4개의 댓글이 있습니다.