[ 백준 ] 1865 웜홀

Link | 1865번 문제 : 웜홀

📌 Analyze

웜홀을 타면 시간이 거꾸로 돌아간다.

한 지점에서 출발하여 다시 돌아올 때 시간이 과거로 가있기 위해서는 음의 사이클이 있어야 한다.

이는 벨만-포드로 확인하면 된다.

단, 어떤 지점에서 출발할 지 모르기 때문에 모든 지점에서 확인해야 한다.

주의할 점은 지점이 연결이 안되어 있을 수도 있기 때문에 모든 지점에서 확인해야 한다.

예를 들어 위의 그림에서 1번을 시작점으로 하여 벨만 포드를 실행하면 음의 사이클을 찾지 못한다.

그럼에도 2와 3에서 음의 사이클이 존재한다.

📌 Solution

Step 1. 문제로부터 Edge들을 읽어서 저장한다.

이때 일반 도로는 양방향이라는 점을 고려하여 저장한다.

while (M-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    int S = Integer.parseInt(tokenizer.nextToken());
    int E = Integer.parseInt(tokenizer.nextToken());
    int T = Integer.parseInt(tokenizer.nextToken());
    edges.add(new Edge(S, E, T));
    edges.add(new Edge(E, S, T));
}

웜홀은 단방향으로 저장하지만 시간이 음수라는 점을 고려한다.

while (W-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    int S = Integer.parseInt(tokenizer.nextToken());
    int E = Integer.parseInt(tokenizer.nextToken());
    int T = Integer.parseInt(tokenizer.nextToken());
    edges.add(new Edge(S, E, -T));
}

Step 2. 각 지점들을 시작점으로 벨만 포드 알고리즘을 적용한다.

public static boolean travel() {
    for (int node = 1; node <= N; node++) {
        D = new int[N + 1];
        Arrays.fill(D, INF);
        D[node] = 0;
        for (int i = 0; i < N - 1; i++) searchEdge();
        int[] d = D.clone();
        searchEdge();
        for (int n = 1; n <= N; n++) if (D[n] != d[n]) return true;
    }
    return false;
}

public static void searchEdge() {
    for (Edge e : edges)
        if (D[e.from] != INF) D[e.to] = Math.min(D[e.to], D[e.from] + e.time);
}

그런데 이런 방식으로 하면 모든 값이 최대치로 주어졌을 때 제한시간을 넘어간다.

제한시간을 지키기 위해서는 이미 음의 사이클을 찾은 상태에서는 해당 테스트 케이스를 종료해야 한다.

public static boolean travel() {
    Loop:
    for (int node = 1; node <= N; node++) {
        D = new int[N + 1];
        Arrays.fill(D, INF);
        D[node] = 0;
        for (int i = 0; i < N - 1; i++) if (!searchEdge()) continue Loop;
        if (searchEdge()) return true;
    }
    return false;
}

public static boolean searchEdge() {
    boolean update = false;
    for (Edge e : edges)
        if (D[e.from] != INF && D[e.to] > D[e.from] + e.time) {
            D[e.to] = D[e.from] + e.time;
            update = true;
        }
    return update;
}

-> 각 node를 돌면서 bellman-ford 실행
-> N - 1번 edge 탐색을 하면서 업데이트가 없으면 다른 node를 시작점으로 재탐색
-> N - 1번 edge 탐색에서 업데이트가 있으면 한 번더 탐색하여 변화가 있으면 음의 사이클 탐색

📌 Code

GitHub Repository

public static int N;
public static int[] D;
public static final List<Edge> edges = new ArrayList<>();
public static final int INF = 5_000_000;

public static void solution() throws IOException {
    int T = Integer.parseInt(reader.readLine());
    while (T-- > 0) {
        init();
        result.append(travel() ? "YES" : "NO").append("\n");
    }
}

public static void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    N = Integer.parseInt(tokenizer.nextToken());
    int M = Integer.parseInt(tokenizer.nextToken());
    int W = Integer.parseInt(tokenizer.nextToken());
    edges.clear();

    while (M-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        int S = Integer.parseInt(tokenizer.nextToken());
        int E = Integer.parseInt(tokenizer.nextToken());
        int T = Integer.parseInt(tokenizer.nextToken());
        edges.add(new Edge(S, E, T));
        edges.add(new Edge(E, S, T));
    }

    while (W-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        int S = Integer.parseInt(tokenizer.nextToken());
        int E = Integer.parseInt(tokenizer.nextToken());
        int T = Integer.parseInt(tokenizer.nextToken());
        edges.add(new Edge(S, E, -T));
    }
}

public static boolean travel() {
    Loop:
    for (int node = 1; node <= N; node++) {
        D = new int[N + 1];
        Arrays.fill(D, INF);
        D[node] = 0;
        for (int i = 0; i < N - 1; i++) if (!searchEdge()) continue Loop;
        if (searchEdge()) return true;
    }
    return false;
}

public static boolean searchEdge() {
    boolean update = false;
    for (Edge e : edges)
        if (D[e.from] != INF && D[e.to] > D[e.from] + e.time) {
            D[e.to] = D[e.from] + e.time;
            update = true;
        }
    return update;
}

static class Edge {

    int from, to, time;

    public Edge(int from, int to, int time) {
        this.from = from;
        this.to = to;
        this.time = time;
    }
}