백준 10282 - 해킹 (JAVA)

다익스트라로 풀었습니다.

풀이방법은 아래에 자세하게 적겠습니다. 

 

 

변수설명

INF : 가장 큰 임의의 숫자 (dist배열에 갱신되기 전 초기에 임시로 넣어주기 위함)
dist[] : 컴퓨터를 최소시간 감염을 저장할 배열
list[] : 각 연결된 노드의 정보를 담을 배열
n : 컴퓨터의 갯수
d : 연결된 노드정보의 갯수
t : 테스트 케이스의 갯수
c : 처음 감염이 된 컴퓨터의 번호

 

 

 

 

1. b가 a에 의존한다고 되어있으므로, start와 end를 반대로 넣어줘야 제대로 동작한다. 

2. INF으로 입력되어 있는 애들은 감염되지 않은 애들이므로, 감염된 컴퓨터를 더해줄 때 제외해야된다. 

3. 어느 컴퓨터가 마지막에 감염되었는지는 알 수 없으므로, 전체 dist[] 리스트를 처음부터 돌면서 가장 큰 숫자를 출력해주면 걔가 마지막에 감염된 컴퓨터가 된다. 

4. 출력해줄때는 "\n"을 마지막에 꼭 붙여넣어주자. 이걸 안써서 오답을 두번 제출했다 ㅠ.ㅠ

 

 

import java.io.*;
import java.util.*;
 
class Node implements Comparable<Node>{
    int end, weight;
 
    public Node(int end, int weight){
        this.end = end;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Node o){
        return weight - o.weight;
    }
}
 
 
public class BJ_Hacking {
    static final int INF = 99999999;
    static int dist[];
    static List<Node> [] list;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int n,d,c,t;
    public static int stoi(String s){return Integer.parseInt(s);}
 
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        t = stoi(st.nextToken()); // 2
 
        for(int test_case=1; test_case<=t; test_case++){
            StringTokenizer s = new StringTokenizer(br.readLine());
            n = stoi(s.nextToken()); // 3
            d = stoi(s.nextToken()); // 2
            c = stoi(s.nextToken()); // 2
 
            list = new ArrayList[n+1];
            dist = new int[n+1];
 
            Arrays.fill(dist, INF);
 
            for(int i=1; i<=n; i++){
                list[i] = new ArrayList<>();
            }
 
            for(int i=1; i<=d; i++){
                StringTokenizer ss = new StringTokenizer(br.readLine());
                int end = stoi(ss.nextToken());
                int start = stoi(ss.nextToken());
                int weight = stoi(ss.nextToken());
 
                list[start].add(new Node(end,weight));
            }
 
            daik(c);
 
            StringBuilder sb = new StringBuilder();
 
            int wasted_computer = 0;
            int max = -1;
            for(int i=1; i<=n; i++){
                if(dist[i] == INF){
                    continue;
                }else{
                    wasted_computer++;
                    max = Math.max(max,dist[i]);
                }
            }
 
            sb.append(wasted_computer + " " + max + "\n");
            bw.write(sb.toString());
            bw.flush();
        }
 
 
    }
 
        public static void daik(int start){
            PriorityQueue<Node> pq = new PriorityQueue();
            boolean visits[] = new boolean[n+1];
            dist[start] = 0;
            pq.add(new Node(start, 0));
 
            while(!pq.isEmpty()){
                Node curnode = pq.poll();
                int next = curnode.end;
                if (visits[next]) continue;
                visits[next] = true;
                for(Node node: list[next]) {
                    if (dist[node.end] > dist[next] + node.weight){
                        dist[node.end] = dist[next] + node.weight;
                        pq.add(new Node(node.end, dist[node.end]));
                    }
                }
            }
 
 
 
 
 
 
    }
 
 
}