[백준]17396: 백도어 - JAVA

[백준]17396: 백도어

17396번: 백도어

풀이

🪑 문제가 좀 복잡해 보여서 그렇지 사실 문제에 필요 없는 정보를 제외하면 그냥 최단거리 문제이당.

 

📝 문제를 푸는데 필요한 조건만 정리해 보자.

• 0에서 N-1번째 분기점 까지 가는 최단 거리를 구해준다.
• 이때 시야 정보도 주어지는데 0이면 해당 분기점일 때 상대 시야에서 보이지 않는다는 의미이고, 1이면 상대 시야에서 보인다는 의미이다.
• 시야에서 보이지 않으면서 N-1번째 분기점으로 갈 수 있는 최단거리를 구하면 된다.

 

🔧 문제를 풀어보자.

1. 각 분기점 사이의 정보를 입력 받는다.
2. 다익스트라 알고리즘을 사용하여 최단거리를 구한다.
3. 출력한다.

 

🔹 각 분기점 사이의 정보를 입력 받는다.

- 분기점 간에 이동할 수 있는 간선의 정보가 주어지며 이때 간선은 양방향으로 이동이 가능하다.

 

🔹 다익스트라 알고리즘을 사용하여 최단거리를 구한다.

- 0번 분기점에서 N-1번 분기점으로 이동하는 최단 거리를 구하는 문제이므로 최단 거리 알고리즘 중에서 다익스트라를 사용한다.

- 다익스트라 탐색시 유의할 점 하나가 있다면 시야에 들어오는 분기점으로는 가지 못하며, 마지막 분기점은 항상 시야에 들어온다는 점이다.

- 경로를 저장하는 배열은 long타입으로 선언해 주었다. (int로 하니 틀렸어서 long으로 고치니 되었다.)

 

🔹 경로가 존재하는지 여부를 확인하여 최단 경로를 출력해 준다.

 

코드

import java.util.*;
 
public class Main {
 
    static int n, m;
    static boolean[] sight;
    static ArrayList<Node>[] list;
    static long[] dist;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        //입력
        n = scan.nextInt();
        m = scan.nextInt();
 
        sight = new boolean[n];
        for(int i = 0; i < n; i++) {
            int flag = scan.nextInt();
            if(flag == 1) sight[i] = true;
            else sight[i] = false;
        }
 
        list = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
 
        for(int i = 0; i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int c = scan.nextInt();
            list[s].add(new Node(e, c));
            list[e].add(new Node(s, c));
        }
        //입력 끝
 
        dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        dijkstra();
 
        if(dist[n - 1] == Long.MAX_VALUE) System.out.println("-1");
        else System.out.println(dist[n - 1]);
    }
 
    public static void dijkstra() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        boolean[] visited = new boolean[n];
        q.offer(new Node(0, 0));
 
        while(!q.isEmpty()) {
            Node current = q.poll();
 
            if(visited[current.node]) continue;
            visited[current.node] = true;
 
            for(int i = 0; i < list[current.node].size(); i++) {
                Node next = list[current.node].get(i);
                if(next.node != n - 1 && sight[next.node]) continue;
                if(dist[next.node] > dist[current.node] + next.cost) {
                    dist[next.node] = dist[current.node] + next.cost;
                    q.offer(new Node(next.node, dist[next.node]));
                }
            }
        }
    }
 
    public static class Node implements Comparable<Node> {
        int node;
        long cost;
 
        public Node(int node, long cost) {
            this.node = node;
            this.cost = cost;
        }
 
        @Override
        public int compareTo(Node n) {
            if(this.cost - n.cost > 0) return 1;
            else return -1;
        }
    }
}