글 읽기 - python 으로 문제 풀이 할 때에 floa('inf') 관련 질문

deserve82 3년 전 0

안녕하세요 벨만 포드 사이클 유무를 cycle로 판별하는 간단한 알고리즘을 작성해 문제를 풀었지만 계속해서 틀렸습니다가 떴습니다.

다른 것을 의심해 보았지만 도저히 정답과 다른 것을 찾을 수 없어서 혹시 몰라 가중치 값들을 초기화 할 때에

float('inf') 말고 22억을 넣었더니 바로 정답 처리가 되더군요.

float('inf')에 대해 찾아보았지만 원하는 답변을 얻을 수 가 없어서 부득이하게 질문 올립니다.

왜 float('inf')는 무한대의 역할을 잘 하는 것 같은데 정답처리가 되지 않고 , 22억은 왜 되는 지 궁금해서 여쭈어 보려 합니다. 감사합니다.

감사합니다.

def send_to_universe():
    is_update = False
    for i in range(N):
        for j in range(N):
            for nx, nxw in graph[j]:
                cost = weights[j] + nxw
                if weights[nx] > cost:
                    weights[nx] = cost
                    if i == N-1:
                        is_update = True
    return is_update


for _ in range(int(input())):
    N, M, W = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        s, e, val = map(int, input().split())
        s -= 1
        e -= 1
        graph[s].append((e, val))
        graph[e].append((s, val))
    for _ in range(W):
        s, e, val = map(int, input().split())
        s -= 1
        e -= 1
        graph[s].append((e, -val))
    
    # 문제의 코드
    # weights = [float('inf')] * N
    weights = [2200000000] * N
    a = False
    for i in range(N):
        if graph[i]:
            weights[i] = 0
            if send_to_universe():
                print("YES")
            else:
                print("NO")
            break

sait2000 3년 전 1

그래프가 연결그래프가 아니면 문제가 되겠네요

wonkyum256 3년 전 3

수학적으로 보면 무한대에 무언가를 더하면 무한대가 됩니다.

하지만 프로그래밍적으로 보면 무한대에 무언가를 더하면 overflow가 발생합니다.

알고리즘 관점에서 보면 경로가 무한대라는 의미는 시작점으로부터 연결되어있지 않다는 의미입니다.

그런데 음수인 사이클을 찾기 위해서는 시작점으로 부터 연결되어있지 않은 정점들도 모두 고려를 해주어야 합니다.

따라서 이런 정점들에 대해서도 계산을 하기 위해서는 적당히 큰 값을 무한대로 설정해주어야 하는데 (사실상 이때부터 무한대가 아니죠)

도로의 개수가 최대 2500개 인데 양방향이므로 5000개, 각 도로별 가중치가 최대 10000이고 웜홀도 고려한다면

무한대를 5000 * 10000 이상으로 두면 적당합니다.

deserve82 3년 전 0

두 분다 너무 감사드립니다. 바로 이해가 되었어요!!!

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

문제

문제

출처

ICPC

python 으로 문제 풀이 할 때에 floa('inf') 관련 질문

deserve82 3년 전 0

sait2000 3년 전 1

wonkyum256 3년 전 3

deserve82 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말