[BOJ] 1865 - 웜홀

김우경·2021년 1월 14일

알고리즘

목록 보기

48/69

문제 링크

문제 설명

N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다.
한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 구하시오.

문제 풀이

간선이 음수이므로 벨만포드 알고리즘을 이용했다.

시도 1

출발점이 주어지지 않아서 포문을 돌면서 모든 노드를 출발점으로 잡고 벨만포드 알고리즘을 돌렸는데 86%에서 시간초과가 났다 ^_ㅠ..

import sys
input = sys.stdin.readline
INF = int(1e9)

def bf(start):
    dist[start] = 0
    pre = dist[start]
    for i in range(n):
        #n번의 라운드 반복
        for j in range(len(edges)):
            now = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if dist[now] != INF and dist[next_node] > dist[now]+cost:
                dist[next_node] = dist[now]+cost
                if dist[start] < pre:
                    return True
                pre = dist[start]
    return False

tc = int(input())
answer = []
for _ in range(tc):
    n, m, w = map(int, input().split())
    edges = []
    flag = False
    for _ in range(m):
        s, e, t = map(int, input().split())
        edges.append((s, e, t))
        edges.append((e, s, t))
    for _ in range(w):
        s, e, t = map(int, input().split())
        edges.append((s, e, t*(-1)))

    for i in range(1, n+1):
        dist = [INF]*(n+1)
        if bf(i):
            flag = True
    if flag == True:
        answer.append("YES")
    else:
        answer.append("NO")
for a in answer:
    print(a)

시도 2

찾아보니 단순하게 그래프 내에 음수 간선 사이클이 있는지 검사하면 된다고 해서 출발점을 1로 두고 벨만포드를 한번 돌렸다.

def bf():
	dist[1] = 0
    for i in range(n):
        #n번의 라운드 반복
        for now, next_node, cost in edges:
            if dist[now] != INF and dist[next_node] > dist[now]+cost:
                dist[next_node] = dist[now]+cost
                if i == n-1:
                    return True
    return False

근데 틀렸습니다가 나온다 왜 ???? 왜지,,,,,,,,,,,,,,,,,,,,,,

시도 3

def bf():
    for i in range(n):
        #n번의 라운드 반복
        for now, next_node, cost in edges:
            if dist[next_node] > dist[now]+cost:
                dist[next_node] = dist[now]+cost
                if i == n-1:
                    return True
    return False

dist[1] = 0으로 출발지점을 1로 설정해주는 부분을 빼고, dist[now] != INF 검사하는 부분을 빼니까 된다. .. . 근데 왜 되는지 모르겠습니다 ^_ㅠ ,,,

전체 코드

import sys
input = sys.stdin.readline
INF = int(1e9)

def bf():
    for i in range(n):
        #n번의 라운드 반복
        for now, next_node, cost in edges:
            if dist[next_node] > dist[now]+cost:
                dist[next_node] = dist[now]+cost
                if i == n-1:
                    return True
    return False

tc = int(input())
answer = []
for _ in range(tc):
    n, m, w = map(int, input().split())
    edges = []
    flag = False
    for _ in range(m):
        s, e, t = map(int, input().split())
        edges.append((s, e, t))
        edges.append((e, s, t))
    for _ in range(w):
        s, e, t = map(int, input().split())
        edges.append((s, e, t*(-1)))

    dist = [INF]*(n+1)
    if bf():
        answer.append("YES")
    else:
        answer.append("NO")
for a in answer:
    print(a)