[백준, Java] 10282번, 해킹 (그래프 탐색, BFS)

문제 링크

10282번: 해킹

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 컴퓨터들에는 단방향 의존관계가 존재합니다.

2. 의존하는 컴퓨터가 감염되면 s초 이후에 의존한 컴퓨터도 감염됩니다.

3. 시작 컴퓨터를 기준으로 마지막 컴퓨터까지 감염되는 시간과 컴퓨터 수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 시작 컴퓨터를 기준으로 BFS로 진행합니다.

 

3. 탐색이 끝났을 때 감염된 컴퓨터 수와 걸린 시간을 결과로 출력합니다.

 

 

컴퓨터 BFS 탐색

 

시작 컴퓨터를 기준으로 BFS탐색을 진행합니다.

 

그래프 형태는 a컴퓨터가 b컴퓨터를 의존하기 때문에

 

a → b의 단방향으로 볼 수 있습니다.

 

 

 

시작 컴퓨터를 기준으로 탐색합니다.

 

 

각 컴퓨터를 방문하는 시간을 기준을 PriorityQueue<>으로 사용해서 지난 시간이 작은 값부터 방문합니다.

 

방문하였을 때,

 

감염된 컴퓨터 수 : +1

 

지난 시간 : 현재 컴퓨터의 수로 초기화합니다.

 

예제입력 1.

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

※ 1번째 테스트케이스가 진행되는 과정만 보여드리겠습니다.

n : 3

d : 2

c : 2

 

 

2. 시작 컴퓨터를 기준으로 BFS로 진행합니다.

 

시작 컴퓨터 : 2

2번 컴퓨터 감염된 후 의존한 컴퓨터들 감염 시작!

1번 컴퓨터는 2번 컴퓨터를 의존하지만,

 

3번 컴퓨터는 의존하는 것이 아닌 2번 컴퓨터가 3번 컴퓨터를 의존하기 때문에!

 

즉, 1번 컴퓨터만 감염이 시작됩니다.

 

1번 컴퓨터를 의존하는 컴퓨터가 없기 때문에 더 이상 감염은 진행되지 않습니다.

 

3. 탐색이 끝났을 때 감염된 컴퓨터 수와 걸린 시간을 결과로 출력합니다.

 

 

5초에 가능한 모든 컴퓨터 감염!!

 

5 을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 컴퓨터 정보와 의존 관계를 저장합니다.
• bfs 함수를 이용하여 시작 컴퓨터 기준 감염을 시작합니다.
• 감염이 끝난 뒤 컴퓨터 개수와 걸린 시간을 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.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    //의존 관계 정보 클래스
    static class Link implements Comparable<Link>{
        int nxt, time;	//nxt : 의존하는 컴퓨터, time : 감염되는 시간
        public Link(int nxt, int time){
            this.nxt = nxt;
            this.time = time;
        }
        //감염되는 시간 기준 오름차순 정렬
        @Override
        public int compareTo(Link o) {
            return this.time - o.time;
        }
    }
    static List<List<Link>> graph;
    static int n;
    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));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        //각 테스트케이스 진행
        for(int tc=0;tc<T;tc++) {
            st = new StringTokenizer(br.readLine()," ");
            graph = new ArrayList<>();
            n = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            //그래프 초기화
            for(int i=0;i<=n;i++)
                graph.add(new ArrayList<>());
            //의존 관계 그래프 저장
            for(int i=0;i<d;i++){
                st = new StringTokenizer(br.readLine()," ");
                int b = Integer.parseInt(st.nextToken());
                int a = Integer.parseInt(st.nextToken());
                int t = Integer.parseInt(st.nextToken());
                graph.get(a).add(new Link(b, t));	//a → b의 의존관계 성립
            }
            int[] result = bfs(c);	//감염을 진행하는 bfs함수 실행
            //모든 감염이 끝난 뒤 감염된 컴퓨터 수와 걸린 시간을 StringBuilder 저장
            sb.append(result[0]).append(" ").append(result[1]).append("\n");
        }
        bw.write(sb.toString());	//모든 결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //감염 진행하는 bfs함수
    static int[] bfs(int start){
        PriorityQueue<Link> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[n+1];	//컴퓨터 감염 확인 배열
        int[] result = new int[2];
        pq.offer(new Link(start, 0));	//시작 컴퓨터 저장
        //감염 진행
        while(!pq.isEmpty()){
            Link cur = pq.poll();
            if(visited[cur.nxt])	//감염된 컴퓨터 방문은 넘기기
                continue;
            else {	//감염되지 않은 컴퓨터일 때
                visited[cur.nxt] = true;	//감염 확인
                result[0]++;	//컴퓨터 수 증가
                result[1] = cur.time;	//시간 변경
            }
            //의존 관계 있는 컴퓨터 방문
            for(Link nxt : graph.get(cur.nxt)){
                if(!visited[nxt.nxt]){	//감염되지 않은 컴퓨터일 때 방문하기
                    pq.offer(new Link(nxt.nxt, cur.time + nxt.time));
                }
            }
        }
        return result;
    }
}