[백준, Java] 28283번, 해킹(BFS, 정렬)

문제 링크

28283번: 해킹

---

 

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. N개의 컴퓨터에서 X개를 동시에 해킹을 진행할 것입니다.

2. 해킹한 컴퓨터는 1분마다 A[i]의 값만큼 수익을 얻을 수 있습니다.

3. 해킹이 시작하고 0.5초 뒤에 B[0]...B[i]의 컴퓨터의 보안 시스템이 설치됩니다.

4. 보안 시스템은 1초마다 연결된 회선으로 확산됩니다.

5. 보안 시스템이 깔리면 해킹된 컴퓨터는 더이상 수익을 얻을 수 없습니다.

6. 무수히 많은 돈을 얻을 수 있다면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 보안 시스템 기준 BFS이후 정렬을 통한 최대 수익(돈)을 구합니다.

 

3. 최대 수익(돈)을 결과로 출력합니다.

 

 

보안 시스템 기준 BFS

 

왜 보안 시스템 기준으로 BFS를 진행하는가?

 

보안 시스템이 설치된 시간 전까지는 해킹을 통해 최대로 벌 수 있는 시간을 구할 수 있습니다.

 

예를 들어.

 

5번 컴퓨터가 5.5초에 보안 시스템이 설치되었다면?

 

→이 컴퓨터를 해킹했을 때 얻을 수 있는 시간은 5분입니다.

 

이렇게 모든 컴퓨터의 보안 시스템을 기준으로 탐색한다면 각 컴퓨터가 해킹에 진행되어 수익을 창출할 시간을 구할 수 있습니다.

 

 

시간을 구한 뒤 각 컴퓨터 해킹을 진행할 때 얻을 수 있는 수익 기준 내림차순 정렬

 

[점화식]

time[] : 보안 시스템 기준 BFS이후 각 컴퓨터가 정보 시스템 설치된 시간

컴퓨터에 해킹을 진행했을 때 얻을 수 있는 수익 : time[i] × 분 당 금액

 

모든 컴퓨터 수익을 내림차순으로 정렬해서 X개를 뽑아서 수익의 합을 구한다면?

 

그 값은 최대 얻을 수 있는 금액입니다.

 

※ 무수히 많아지는 경우

 

보안 시스템이 설치되지 않았으며, 금액이 0보다 큰 값일 때

 

0보다 큰 값인 값을 확인하는 이유

→ 0원이면 보안 시스템이 설치되지 않아 무제한으로 금액을 창출해도 0원이기 때문입니다.

※예제 입력 과정을 확인하시면 이해하시기 편하실 것입니다.

예제입력 1.

1. 입력된 정보를 저장합니다.

N : 5

M : 4

 

X : 2

 

Y : 3

A[] : 1 10 100 1000 10000

B[] : 2 3 5​

 

컴퓨터 연결 그래프

 

2. 보안 시스템 기준 BFS이후 정렬을 통한 최대 수익(돈)을 구합니다.

 

보안 시스템 설치 시작!!

B[] : 2, 3, 5

 

설치 시간

 

1	2	3	4	5
	0(0.5)	0(0.5)		0(0.5)

 

1분 후 확산

설치 시간

1	2	3	4	5
	0(0.5)	0(0.5)	1(1.5)	0(0.5)

 

2분 후 확산

 

설치 시간

1	2	3	4	5
2(2.5)	0(0.5)	0(0.5)	1(1.5)	0(0.5)

 

연결된 모든 컴퓨터 보안 시스템 설치 완료 및 BFS 탐색 종료!

 

점화식을 통한 모든 컴퓨터의 기대 금액 구하기

 

	1	2	3	4	5
A[]	1	10	100	1000	10000
Time[]	2	0	0	1	0
수익	1 × 2 = 2	10 × 0 = 0	100 × 0 = 0	1000 × 1 = 1000	10000 × 0 = 0

 

수익 내림차순 X(2)개 뽑기

 

1번 컴퓨터, 4번 컴퓨터

 

수익 : 1번(2) + 4번(1000) = 1002

 

3. 최대 수익(돈)을 결과로 출력합니다.

 

 

 

최대 수익 : 1002

 

1002을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 컴퓨터 및 금액 등의 정보를 저장합니다.
• bfs() 함수를 실행하여 정보 시스템 기준 BFS을 진행합니다.
• 점화식을 통해 모든 컴퓨터 가능한 수익을 내림차순 정렬하는 PriorityQueue에 저장합니다.
• 저장할 때 무수히 많은 금액이 추가되는 경우 결과를 -1로 설정한 뒤 출력을 준비합니다.
• 무수히 많은 금액이 아닌 경우 수익이 큰 기준 X개를 더해서 결과를 구합니다.
• 진행했던 결과를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• bfs함수는 정보 시스템 기준 BFS을 진행하는 함수입니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    //BFS에서 사용할 InnerClass
    static class Info implements Comparable<Info>{
    	//idx : 컴퓨터 번호, time : 보안 시스템 설치 시간
        int idx, time;
        public Info(int idx, int time){
            this.idx = idx;
            this.time = time;
        }
        //보안 시스템 설치시간 기준 오름차순 정렬
        @Override
        public int compareTo(Info o) {
            return this.time - o.time;
        }
    }
    //연결 회선 저장 리스트
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;	//보안 시스템 설치 확인 배열
    static int[] time, secureCom;	//설치 시간 및 초기 보안 컴퓨터 저장 배열
    static long[] money;	//분 당 금액 저장 배열
    static int N,Y;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        // 입력값 저장
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());
        visited = new boolean[N+1];
        money = new long[N+1];
        time = new int[N+1];
        secureCom = new int[Y+1];
        for(int i=0;i<=N;i++)
            graph.add(new ArrayList<>());
        st = new StringTokenizer(br.readLine(), " ");
        //분 당 금액 저장
        for(int i=1;i<=N;i++)
            money[i] = Long.parseLong(st.nextToken());
            
        //양방향 회선 정보 저장
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            graph.get(c1).add(c2);
            graph.get(c2).add(c1);
        }
        st = new StringTokenizer(br.readLine()," ");
        //초기 보안 컴퓨터 저장
        for(int i=0;i<Y;i++)
            secureCom[i] = Integer.parseInt(st.nextToken());
        long result = 0;
        bfs();	//보안 시스템 기준 BFS 탐색
        //모든 수익 내림차순 정렬할 PriorityQueue
        PriorityQueue<Long> total = new PriorityQueue<>(Collections.reverseOrder());
        //무수히 많아지는 경우 확인 Flag
        boolean fail_flag = true;
        //모든 컴퓨터 가능 수익 창출 확인
        for(int i=1;i<=N;i++) {
            //무수히 많은 금액 창출할 때
            if(!visited[i] && money[i] > 0){
                fail_flag = false;
                result = -1;
                break;
            }
            total.add(time[i] * money[i]);
        }
        //무수히 많은 금액 창출하지 않을 때
        //가장 높은 수익 X개 구해서 더하기
        if(fail_flag){
            for(int i=0;i<X;i++)
                result += total.poll();
        }
        //결과 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //보안 시스템 기준 BFS 탐색 진행하는 함수
    static  void bfs() {
        //BFS에 사용할 PriorityQueue
        PriorityQueue<Info> pq = new PriorityQueue<>();
        //초기 보안 컴퓨터 설치
        for (int i = 0; i < Y; i++) {
            int secIdx = secureCom[i];
            pq.add(new Info(secIdx, 0));
            visited[secIdx] = true;
        }
        //BFS 탐색으로 회선으로 보안 시스템 확장
        while (!pq.isEmpty()) {
            Info cur = pq.poll();
            for (int nxt : graph.get(cur.idx)) {
                if (!visited[nxt]) {
                    visited[nxt] = true;
                    time[nxt] = cur.time + 1;
                    pq.add(new Info(nxt, time[nxt]));
                }
            }
        }
    }
}