백준 10282번 해킹 [JAVA]

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.

각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

 

출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

 

예제

 

풀이 방법

해커로부터 컴퓨터를 해킹해 서로 의존하는 컴퓨터들이 모두 감염되는 시간과, 감염된 컴퓨터의 수를 구하는 문제였습니다.

 

저는 배열과 리스트 두 가지 방식으로 다익스트라 알고리즘을 이용해 문제를 해결했습니다.

 

1) 연결되어 있는 컴퓨터 정보 배열/리스트에 저장

2) 컴퓨터간의 감염시간을 저장할 distance 배열 큰 수로 초기화

3) 다익스트라 알고리즘을 이용해 최소 감염시간 distance배열에 저장

4) 감염되는 시간 및 감염된 컴퓨터 수를 구하기 위해 distance배열 값이 INF가 아닌 경우 count++ 및 distance 최댓값 구하기

5) count 및 최대 distance 값 출력

 

코드 (배열)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_BJ_10282_해킹_array {
    
    static class info{
        int end, time;
 
        public info(int end, int time) {
            super();
            this.end = end;
            this.time = time;
        }
 
    }
    
    static int INF = Integer.MAX_VALUE;
    static boolean[] visited;
    static List<info> list[];
    static int [] distance;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=0; tc<T;tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            list = new ArrayList[n+1];
            distance = new int[n+1];
            visited = new boolean[n+1];
            
            for(int i=1;i<=n;i++) list[i] = new ArrayList<>();
            
            for(int i=0;i<d;i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());
                
                list[b].add(new info(a,s));
            }
            
            Arrays.fill(distance, INF);
            distance[c]=0;
            
            int min, current = 0;
            for(int i=0; i<n;i++) {
                min = Integer.MAX_VALUE;
                current = -1;
                for(int j=1;j<n+1;j++) {
                    if(!visited[j] && distance[j]<min) {
                        min = distance[j];
                        current =j;
                    }
                }
                if(current == -1) break;
                
                for(info next : list[current]) {
                    if(!visited[next.end] && distance[next.end]> distance[current]+next.time) {
                        distance[next.end] = distance[current] + next.time;
                    }
                }
                visited[current] = true;
            }
            
            int count=0, max=0;
            for(int i=1;i<distance.length;i++) {
                if(distance[i]!=INF) {
                    count++;
                    max = Math.max(max, distance[i]);
                }
                
            }
            sb.append(count+" "+max+"\n");
        }
        System.out.println(sb.toString());
    }
 
}

 

코드 (리스트)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_BJ_10282_해킹_list {
    
    static class info{
        int end, time;
 
        public info(int end, int time) {
            super();
            this.end = end;
            this.time = time;
        }
 
    }
    
    static int INF = Integer.MAX_VALUE;
    static boolean[] visited;
    static ArrayList<ArrayList<info>> list;
    static int [] distance;
    static PriorityQueue<info> pq = new PriorityQueue<>(new Comparator<info>() {
 
        @Override
        public int compare(info o1, info o2) {
            return o1.time-o2.time;
        }
    });
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=0; tc<T;tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            list = new ArrayList<>();
            distance = new int[n+1];
            visited = new boolean[n+1];
            
            for(int i=0;i<=n;i++) list.add(new ArrayList<>());
            
            for(int i=0;i<d;i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());
                
                list.get(b).add(new info(a,s));
            }
            
            Arrays.fill(distance, INF);
            
            distance[c]=0;
            
            pq.add(new info(c,0));
            while(!pq.isEmpty()) {
                info temp = pq.poll();
                if(visited[temp.end]) continue;
                visited[temp.end]= true;
                
                for(info node : list.get(temp.end)) {
                    if(distance[node.end]>distance[temp.end]+node.time) {
                        distance[node.end] = distance[temp.end]+node.time;
                        pq.add(new info(node.end,distance[node.end]));
                    }
                }
            }
            
            
            int count=0, max=0;
            for(int i=1;i<distance.length;i++) {
                if(distance[i]!=INF) {
                    count++;
                    max = Math.max(max, distance[i]);
                }
                
            }
            sb.append(count+" "+max+"\n");
        }
        System.out.println(sb.toString());
    }
 
}