[코테 매일 풀기 15일차] 1125

백준 10282 해킹

아이디어

• 입력 : 테스트 케이스 T만큼 반복하고, n: 컴퓨터 개수 / d: 간선개수 / c: 시작 번호
• 자료 구조 ArrayList[] list로 각 1부터..n까지의 list 초기화 시켜야함 !
• 간선 입력
• dist거리 선언하고, max_value로 초기화 ->dist[c] =0으로 초기화
• PriorityQueue pq 선언하고 오름차순 정렬
  pq.offer(new Node(c, 0));//거리 w를 0으로 초기화

• //while(큐가 빌때까지): 
  	Node cur = pq.poll()l; //현재 노드 빼내오기
  	int curV = cur.v; //현재 정점
  	int curD = cur.w; //현재 거리 
  //이미 처리된 노드이면 continue 
  //현재 노드와 연결된 간선 탐색 
  	//누적 거리 
  	// 더 짧은 노드 발견하면 갱신하고, 새로운 노드 큐에 넣기 

코드

package boj_gold.p10282_해킹;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node{
  int v;
  int w;

  public Node(int v, int w){
      this.v = v;
      this.w =w;
  }
}
public class Main {
  static int[] dist;
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());

      int T = Integer.parseInt(st.nextToken());
      StringBuilder sb = new StringBuilder();

      for(int i = 0; i < T; i++){
          st = new StringTokenizer(br.readLine());
          int n = Integer.parseInt(st.nextToken());// 컴퓨터 개수
          int d = Integer.parseInt(st.nextToken()); //간선 개수
          int c =  Integer.parseInt(st.nextToken()); //시작 번호

          ArrayList<Node>[] list = new ArrayList[n+1];
          //그래프 초기화
          for (int j= 1; j<=n; j++){
              list[j] = new ArrayList<>();
          }
          //간선 입력
          for (int j = 0; j< d; j++){
              st = new StringTokenizer(br.readLine());
              int v = Integer.parseInt(st.nextToken());
              int u = Integer.parseInt(st.nextToken());
              int w = Integer.parseInt(st.nextToken());
              list[u].add(new Node(v,w));
          }

          // 입력받기
          //각 dist초기화하기
          dist = new int[n+1];
          Arrays.fill(dist, Integer.MAX_VALUE);  //dist 초기화한후 min으로 업데이트 한다.
          //처음 값 초기화
          dist[c] = 0;

          //prioirty Queue로 가중치 오름추순 정렬
          PriorityQueue<Node> pq = new PriorityQueue<>((a,b)-> a.w-b.w);
          pq.offer(new Node(c, 0)); //거리를 0으로 초기화

          //pq가 빌때까지 반복
          while(!pq.isEmpty()){
              //큐
              Node cur = pq.poll();
              int curV = cur.v; //현재 정점
              int curD = cur.w; //현재 거리

              //이미 처리된 노드이면 continue
              if (curD > dist[curV]){
                  continue;
              }
              //현재 노드와 연결된 간선 탐색
              for (Node next: list[curV]){
                  int nextV = next.v;
                  int nextD = curD + next.w; //누적 거리

                  //더 짧은 노드 발견하면 갱신
                  if(nextD < dist[nextV]){
                      dist[nextV] = nextD;
                      pq.offer(new Node(nextV, nextD));
                  }
              }
          }//while
          //출력을 해야하는데: 감염된 컴퓨터 수와 마지막 감염 시간
          int cnt= 0;
          int time = 0; //마지막 감염 시간

          for (int j = 1; j <=n; j++){
              //dist가 업데이트가 된 것
              if (dist[j] != Integer.MAX_VALUE){
                  cnt++;
                  time = Math.max(time, dist[j]);
              }
          }//for
          sb.append(cnt).append(" ").append(time).append("\n");




       }//for 
      System.out.println(sb);


  }
}