글 읽기 - 런타임 에러가 납니다.

bahamoth 7년 전 0

안녕하세요. 수고가 많으십니다.

제 로컬환경에서는 정상적으로 동작하는 소스코드인데 런타임 에러가 납니다.

런타임에러 메세지가 뭔지 알면 단서라도 찾아보겠는데 메세지가 뭔지 모르니 알 수가 없습니다.

python3.5.2 에서 실행하였으며, 소스는 아래에 동봉합니다.

import sys
import copy

mapSize = 0
pathMap = []
endList = []

def initialize():
    global mapSize, pathMap
    mapSize = int(sys.stdin.readline())
    # print(mapSize)
    for iter in range(mapSize):
        line = str(sys.stdin.readline())
        tmp = [int(x) for x in line.split()]
        pathMap.append(tmp)
        # print(tmp)

def testInit():
    global mapSize, pathMap
    mapSize = 3
    pathMap = [[12,-10,70],[-20,20,-20],[19,100,7]]

def findPath(stack, checkedPath):
    # print("stack: "+str(stack))
    # print("checked path: "+str(checkedPath))
    if len(stack) == 0:
        return
    if isGoal(stack[-1]):
        endList.append(copy.deepcopy(stack))
        checked = stack.pop()
        checkedPath.append([tuple(stack[-1]), checked])
        findPath(stack, checkedPath)
    tmpEval = None
    if len(stack) > 0:
        tmpEval = evalPath(stack, checkedPath)
        if tmpEval is not None:
            stack.append(tmpEval)
        checked = stack.pop()
        if len(stack) > 0:
            checkedPath.append([tuple(stack[-1]), checked])
    findPath(stack, checkedPath)

def isGoal(elem):
    # print("goal pathMap:{0}".format(pathMap))
    if elem[0] == len(pathMap)-1 and elem[1] == len(pathMap)-1:
        # print("isGoal True mapSize:{0}, elem:{1}".format(len(pathMap)-1, elem))
        return True
    # print("isGoal False mapSize:{0}, elem:{1}".format(len(pathMap)-1, elem))
    return False

def isGraph(stack, current, tmpEval):
    tmpChecked = list(zip(stack[0::2], stack[1::2]))
    # print(">>>>"+str(tmpChecked))
    if (current, tmpEval) in tmpChecked:
        # print("graph true: {0} in {1}".format((current,tmpEval), tmpChecked))
        return True
    # print("graph false: {0} in {1}".format((current, tmpEval), tmpChecked))
    return False

def isVisited(stack, tmpEval):
    if tmpEval in stack:
        return True
    return False

def evalPath(stack, checkedPath):
    current = stack[-1]
    prev = None
    if len(stack)>1:
        prev = stack[-2]
    # print("current:{0}, prev:{1}".format(current, prev))
    tmpEval = [(x,y) for x,y in
            [(current[0]-1,current[1]),
             (current[0]+1,current[1]),
             (current[0],current[1]-1),
             (current[0],current[1]+1)]
               if x >=0 and y>=0 and (x,y) != prev and x < mapSize and y < mapSize]
    tmpEval = [(x,y) for x,y in tmpEval
               if not [current, (x,y)] in checkedPath
               and not isGraph(stack,current,(x,y))
               and not isVisited(stack, (x,y))]
    # print("eval path candidates:{0}".format(tmpEval))
    if len(tmpEval) == 0:
        return None
    return sorted(tmpEval, key=lambda x: pathMap[x[0]][x[1]], reverse=True)[0]

def findpathOnce(stack, checkedPath):
    global pathMap
    # print("stack: "+str(stack))
    if isGoal(stack[-1]):
        return
    tmpEval = evalPath(stack, checkedPath)
    if tmpEval is not None:
        stack.append(tmpEval)
    else:
        checked = stack.pop()
        checkedPath.append([tuple(stack[-1]), checked])
        # print(">>> checkedPath:"+str(checkedPath))
    findpathOnce(stack, checkedPath)

initialize()
#testInit()
start = [(0,0)]
checkedPath = []
findpathOnce(start, checkedPath)
a = copy.deepcopy(start)
# print("first path: {0}".format(a))
endList.append(a)
checked = start.pop()
checkedPath.append([tuple(start[-1]), checked])
findPath(start, checkedPath)
#print("paths: "+str(endList))

sol = [sum([pathMap[x[0]][x[1]] for x in iter]) for iter in endList]
solIndex = sorted(range(len(sol)), key=lambda x: x in sol)[0]
#print("sol index :{0}".format(solIndex))
print("{0}".format(max(sol)))

solPath = []
iter = endList[solIndex]
for i in range(len(iter)-1):
    if iter[i][0] == iter[i+1][0] and iter[i][1] < iter[i+1][1]:
        solPath.append("R")
    elif iter[i][0] == iter[i+1][0] and iter[i][1] > iter[i+1][1]:
        solPath.append("L")
    elif iter[i][0] < iter[i+1][0] and iter[i][1] == iter[i+1][1]:
        solPath.append("D")
    elif iter[i][0] > iter[i+1][0] and iter[i][1] == iter[i+1][1]:
        solPath.append("U")
    else:
        solPath.append("?")
print(str.join("", solPath))

zlzmsrhak 7년 전 0

죄송하지만 이렇게 빽빽한 130줄짜리 코드에 설명 한 줄 없고, 문제도 푼 사람이 없을 만큼 어려운 문제라서

저를 포함해서 답글 달 수 있는 사람은 없을 것 같습니다.

함수 명만 보고 답글 달아드리면, 만약 DFS로 전수조사하는 방식으로 풀고 계시는 것이라면, 시간 내에 나오지 않거나 답이 나오지 않을 것입니다.

추가로, 격자라는 특징을 이용하지 않고 그래프로 바꿔서 풀고 계신다면, 헤밀턴 경로 찾는 문제와 같아지기 때문에 풀리지 않습니다.

bahamoth 7년 전 0

댓글 감사합니다.

제 환경에서는 발생하지 않는 런타임 에러가 뭔지 궁금하여 올린 질문이었는데

적어주신 답글로부터 이 문제가 그리 쉽지 않은 문제라는걸 알게 되어

다시 확인해보니 제가 입력 조건을 잘못 알고 있었네요.

위와 같이 풀면 행렬 사이즈가 커졌을 때 recursion limit 를 초과하여 런타임 에러가 발생합니다.

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

문제

문제

출처

ICPC

런타임 에러가 납니다.

bahamoth 7년 전 0

zlzmsrhak 7년 전 0

bahamoth 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말