글 읽기 - 런타임 오류의 원인을 못 찾겠습니다..

cjstjdgur123 4년 전 0

아래 질문에 큰 힌트를 주신 분 덕에 갈피를 잡아 만들게 됐습니다.

그러나 60%정도 진행 이후 계속해서 런타임 오류가 발생하지만 감이 전혀 오지 않아 글써보게됐습니다.

나름 읽기 편하게 클래스를 명시하고 주석도 달아보았는데 혹시나 호기심 가신다면 한 번 같이 고민해봐주셨으면 좋겠습니다.. :)

import sys
sys.setrecursionlimit(250000)

# 절대값을 구하기위한 람다함수 
abs = lambda x: x if x > 0 else -x

# 체크포인트 Flag로 이름 붙임, 서로 연결할때 id 값이 낮은 Flag를 부모개체로 연결하여 그래프 만들었음
# x, y는 플래그 위치 
class Flag (object):
    def __init__(self, id, x, y):
        self.id = id
        self.x = x
        self.y = y
        self.parent = self
    def getMaster(self): # 같은 그래프 내 가장 id가 작은 친구 구함 (서로 같은 그래프인지 확인하기 위함)
        if self.parent == self:
            return self
        self.parent = self.parent.getMaster()
        return self.parent
    def combine(self, who): # A.combine(B)로 두 flag를 연결함 
        if who.getMaster().id < self.getMaster().id:
            self.getMaster().parent = who.getMaster()
        elif who.getMaster().id > self.getMaster().id:
            who.getMaster().parent = self.getMaster()
    def isCombined(self, who): # A.isCombined(B)로 두 flag가 연결돼있는지 여부를 확인함 
        return who.getMaster().id == self.getMaster().id
    def __repr__(self):
        return "({}, {})".format(self.x, self.y)

# 쿼리를 만들었음. before Flag에서 after Flag로 가기에 hp로 충분한지 질의문 그 자체 
class Query (object):
    def __init__(self, id, before, after, hp):
        self.id = id
        self.before = before
        self.after = after
        self.hp = hp
    def __repr__(self):
        return "({}->{}, {} => {})".format(self.before, self.after, self.hp, self.answer)

# before Flag에서 after Flag가 연결되려면 cost 만큼의 hp가 필요함을 의미함
class Relation (object):
    def __init__(self, before, after, cost):
        self.before = before
        self.after = after
        self.cost = cost
    def __repr__(self):
        return "[{} to {}, {}]".format(self.before, self.after, self.cost)

N, Q = map(int, sys.stdin.readline().strip().split())

# 체크포인트 담기 
flags = []
for n in range(N):
    x, y = map(int, sys.stdin.readline().strip().split())
    flags.append( Flag( n, x, y ) )
    
# 쿼리 담기 
querys = []
for q in range(Q):
    before, after, hp = map(int, sys.stdin.readline().strip().split())
    before -= 1
    after -= 1
    querys.append( Query( q, flags[before], flags[after], hp ) )
querys.sort(key=lambda q: q.hp) #쿼리 정렬 

# print( flags ) #테스트
# print( querys )

# X, Y로 정렬했을때 인접한 것을 우선으로 관계를 담음. hp가 올라감에따라 연결하기 위함
relations = []
flags.sort(key=lambda f: f.x)
for i in range(N-1):
    if abs(flags[i+1].x - flags[i].x) <= abs(flags[i+1].y - flags[i].y):
        relations.append( Relation(flags[i], flags[i+1], abs(flags[i+1].x - flags[i].x)) )
flags.sort(key=lambda f: f.y)
for i in range(N-1):
    if abs(flags[i + 1].x - flags[i].x) > abs(flags[i + 1].y - flags[i].y):
        relations.append( Relation(flags[i], flags[i+1], abs(flags[i+1].y - flags[i].y)) )
relations.sort(key=lambda r: r.cost, reverse=True)

currentCost = 0 # 현재 hp 
result = [ False for i in range(Q) ] # YES NO 출력할 것을 담아 두기 위함 
for q in range(Q): # cost대로 오름차순 쿼리를 하나씩 열어봄  
    currentCost = querys[q].hp; # 체력을 업데이트 
    while relations and relations[-1].cost <= currentCost: # 연결할 수 있는 관계가 있고, 지금 그 HP를 만족한다면 가능한 만큼 연결해둠
        rel = relations.pop()
        rel.before.combine( rel.after )
    result[querys[q].id] = querys[q].before.isCombined( querys[q].after ) # 업데이트된 HP로 연결가능한 것을 모두 연결했으면 쿼리에 제시된 두 Flag 연결 여부를 담아둠 

# 담아둔대로 출력 
for b in result:
    if b:
        sys.stdout.writelines("YES\n")
    else:
        sys.stdout.writelines("NO\n")

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

문제

문제

출처

ICPC

런타임 오류의 원인을 못 찾겠습니다..

cjstjdgur123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말