[BOJ] 2606 - 바이러스 (Java)

알고리즘

• 그래프 이론

• 그래프 탐색

• 너비 우선 탐색

• 깊이 우선 탐색

1. 문제

//예제 입력
7
6
1 2
2 3
1 5
5 2
5 6
4 7

//예제 출력
4

2. Idea

• 배열의 index: 컴퓨터의 번호

• 해당 index의 내용: 해당 컴퓨터와 연결된 컴퓨터들의 번호

• 배열로 이어진 그래프는 무방향으로 이루어져야 함을 주의

• 예제 입력에 따른 배열 결과

  [2,5], [1,3,5], [2], [7], [1,2,6], [5], [4]

3. 풀이

3.1. 변수 선언 및 초기화

• int N: 컴퓨터의 수

• int P: 총 간선 수

• ArrayList[] arr: index의 내용=해당 컴퓨터와 연결된 컴퓨터들의 번호

• ArrayList result: 1번 컴퓨터로 인해 바이러스에 걸리게 되는 컴퓨터들의 번호

private static int N;
private static int P;
private static ArrayList<Integer>[] arr;
private static ArrayList<Integer> result;

3.2. arr 생성

각 index마다 ArrayList 할당

for(int i=1; i<=N; i++){
	arr[i]=new ArrayList<>();
}

3.3. 연결된 컴퓨터들의 간선 배열에 할당

• 연결된 컴퓨터에 따라 배열에 번호 add

for(int i=1; i<=P; i++){
	StringTokenizer st=new StringTokenizer(sc.nextLine());
	int num1=Integer.parseInt(st.nextToken());
	int num2=Integer.parseInt(st.nextToken());
	arr[num1].add(num2);
	arr[num2].add(num1); //무방향 그래프이므로 index num1,num2 양쪽에 add
}

3.4. result 배열 할당

• 1번 컴퓨터 arr[1]에 해당된 ArrayList 내의 요소(1번 컴퓨터와 직접적으로 연결된 컴퓨터 번호)들을 result 배열에 add

• reult 배열의 요소들: 1번으로 인해 바이러스에 걸린 컴퓨터들과 연결된 번호들이 배열 형태로 저장

for(int i=0; i<arr[1].size();i++){
	result.add(arr[1].get(i));
}

3.5. result 배열 순회 및 배열 해제/중복 요소 제거

int check_index=0;
while(true){
	if(check_index == result.size()){break;}
	ArrayList<Integer> newElements = new ArrayList<>();
	for (int i = 0; i < result.size(); i++) {
		newElements.addAll(arr[result.get(i)]);
	}
	result.addAll(newElements);
	result=(ArrayList<Integer>)result.parallelStream().distinct().collect(Collectors.toList());
	check_index++;
}

3.6. 결과 출력

• 1을 제거한 후의 size 출력

result.remove(Integer.valueOf(1));
System.out.print(result.size());

4. 전체코드

//Silver_바이러스
import java.util.*;
import java.util.stream.Collectors; //Collectors는 java 8부터 사용 가능

public class BOJ_2606 {
    private static int N;
    private static int P;
    private static ArrayList<Integer>[] arr;
    private static ArrayList<Integer> result;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        N=Integer.parseInt(sc.nextLine());
        P=Integer.parseInt(sc.nextLine());
        arr = new ArrayList[N+1];
        result=new ArrayList<>();

        for(int i=1; i<=N; i++){
            arr[i]=new ArrayList<>();
        }

        for(int i=1; i<=P; i++){
            StringTokenizer st=new StringTokenizer(sc.nextLine());
            int num1=Integer.parseInt(st.nextToken());
            int num2=Integer.parseInt(st.nextToken());
            arr[num1].add(num2);
            arr[num2].add(num1); //무방향 그래프이므로 index num1,num2 양쪽에 add
        }

        for(int i=0; i<arr[1].size();i++){
            result.add(arr[1].get(i));
        }

        int check_index=0;
        while(true){
            if(check_index== result.size()){break;}
            ArrayList<Integer> newElements = new ArrayList<>();
            for (int i = 0; i < result.size(); i++) {
                newElements.addAll(arr[result.get(i)]);
            }
            result.addAll(newElements);
            result=(ArrayList<Integer>) result.parallelStream()
                    .distinct().collect(Collectors.toList());
            check_index++;
        }

        result.remove(Integer.valueOf(1));
        System.out.print(result.size());
    }
}