[BOJ] 1865 웜홀

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 

https://www.acmicpc.net/problem/1865

1865번: 웜홀

---

📍 고려해야할 점

• 한 지점에서 출발하여 다시 출발했던 지점으로 돌아왔을 때 처음 출발했을 때보다 시간이 되돌아가 있는 경우 판단 ➔ 웜홀 내에서 시간이 거꾸로 흘러간다. ➡️ 음수 가중치 존재 & 음의 사이클 존재 O
• 한 지점에서 출발한다. (특정 지점에서 출발 X) 
  • 임의의 정점에서 출발 
    
  • 모든 정점에서 출발
• 두 지점을 연결하는 도로가 한 개보다 많을 수 있다. ➔ 인접 리스트로 구현
• 두 지점 사이의 도로는 양방향이고, 웜홀은 단방향이다. 
• 음의 사이클 있으면 YES
• 음의 사이클 없으면 NO

 

1️⃣ 임의의 정점에서 출발

if (dist[info.end] > dist[j] + info.weight) {
    dist[info.end] = dist[j] + info.weight;
    isUpdate = true;
}

dist[j] != INF 조건이 있으면 출발점에서 다른 정점으로의 간선이 없어서(단절된 곳) INF인 경우, 다른 정점들에서 음수 사이클이 만들어져도 더이상 탐색하지 못하고 NO를 출력하게 된다. 그러므로 조건을 제거하고 위와 같이 코드를 작성해야 한다. 

 

2️⃣ 모든 정점에서 출발

if (dist[j] != INF && dist[info.end] > dist[j] + info.weight) {
    dist[info.end] = dist[j] + info.weight;
    isUpdate = true;
}

특정 정점에서 간선이 없어서 탐색하지 못해도 다른 정점들에서 탐색 가능하므로 조건을 넣어서 코드를 작성한다. 

 

 

🕹️ 풀이과정

1️⃣ 간선과 정점의 정보를 저장한다.

2️⃣ 정점 수만큼 벨만포드 알고리즘을 수행한다.

 

 

 

👩‍💻 전체 코드

public class BOJ_1865_웜홀 {

    static int n, m, w; // n=지점의 수, m=도로의 수, w=웜홀의 수
    static ArrayList<Info>[] graph;
    static int INF = 1000000000;
    static int[] dist;

    static class Info{
        int e, t;

        public Info(int e, int t) {
            this.e = e;
            this.t = t;
        }
    }

    static boolean bellmanFord(){
        dist[1] =0;

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < graph.length; j++) {
                for (Info next : graph[j]) {
                    if (dist[next.e] > dist[j] + next.t) {
                        dist[next.e] = dist[j] + next.t;
                    }
                }
            }
        }

        for (int j = 1; j < graph.length; j++) {
            for (Info next : graph[j]) {
                if (dist[next.e] > dist[j] + next.t) {
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int TC = Integer.parseInt(br.readLine());

        for (int i = 0; i < TC; i++) {

            st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            dist = new int[n + 1];
            Arrays.fill(dist, INF);
            graph = new ArrayList[n + 1];

            for (int j = 0; j < n + 1; j++) {
                graph[j] = new ArrayList<>();
            }


            // 도로의 정보
            //  S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간
            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());

                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                int t = Integer.parseInt(st.nextToken());

                graph[s].add(new Info(e, t));
                graph[e].add(new Info(s, t));
            }

            // 웜홀의 정보
            for (int j = 0; j < w; j++) {
                st = new StringTokenizer(br.readLine());

                int s = Integer.parseInt(st.nextToken()); // 시작 지점
                int e = Integer.parseInt(st.nextToken()); // 도착 지점
                int t = Integer.parseInt(st.nextToken()); // 줄어드는 시간

                graph[s].add(new Info(e, -t));
            }

            if (bellmanFord()) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

 

 

 

 

 

참고

https://steady-coding.tistory.com/91

https://sorjfkrh5078.tistory.com/30