백준 2606 - 바이러스 (자바 - 그래프)

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

* 문제 요약

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 아래의 그림과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2,3,5,6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

 

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다, 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고, 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

* 출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

* 예시

 

* 해결 과정

꽤 옛날에 처음으로 그래프 탐색 알고리즘을 공부했을 때 한 번 풀어서 통과를 받았으나 최근에 재채점으로 런타임 에러를 받은 김에 다시 풀어보았다.

해시맵 자료구조를 이용해 입력받은 데이터들을 기반으로 그래프의 형태를 저장해주었다. 여기서 그래프는 양방향으로 연결된 그래프임을 유의하여, 연결 데이터가 하나 들어오면 해시맵에서 첫 번째 데이터에 두 번째 데이터를 연결하는 것과 두 번째 데이터에 첫 번째 데이터를 연결하는 것, 총 두 가지 경우의 형태를 모두 저장해준다.

 

해시맵에 그래프가 저장되고 나면 bfs(int i) 메소드를 수행해준다. 여기서 1번 컴퓨터가 바이러스에 감염되었을 경우 같이 감염되는 컴퓨터의 갯수를 구해야 하기 때문에 i 에는 탐색 시작 노드값 1이 들어간다.

bfs() 메소드 내부에서는 1번 컴퓨터는 제외시켜야 하므로 만약 needVisit 큐에서 꺼낸 데이터가 1인 경우 감염된 컴퓨터의 갯수를 표현하는 변수 count 의 값을 증가시키지 않고, 만약 1이 아닌 경우 count 를 1 증가시켜준다.

이후는 인접리스트로 BFS 알고리즘을 구현하는 것과 동일한 코드를 작성해주면 된다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws IOException {
		new Main().solution();
	}

	static HashMap<Integer, Queue<Integer>> network = new HashMap<>();
	static boolean[] visited;
	static int count = 0;

	private void solution() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		visited = new boolean[n + 1];
		int connect = Integer.parseInt(br.readLine());

		for (int i = 0; i < connect; i++) {
			String[] input = br.readLine().split(" ");
			int a = Integer.parseInt(input[0]);
			int b = Integer.parseInt(input[1]);

			Queue<Integer> queueA = new LinkedList<>();
			Queue<Integer> queueB = new LinkedList<>();
			if (network.containsKey(a)) {
				queueA = network.get(a);
			}
			queueA.offer(b);
			network.put(a, queueA);

			if (network.containsKey(b)) {
				queueB = network.get(b);
			}
			queueB.offer(a);
			network.put(b, queueB);
		}

		bfs(1);

		bw.write(count + "\n");
		bw.flush();
		bw.close();
		br.close();
	}

	private void bfs(int i) {
		Queue<Integer> needVisit = new LinkedList<>();
		needVisit.offer(i);
		visited[i] = true;

		while (!needVisit.isEmpty()) {
			int computer = needVisit.poll();
			if (computer != i) {
				count++;
			}
			Queue<Integer> queue = new LinkedList<>();
			if (network.containsKey(computer)) {
				queue = network.get(computer);
			}
			if (queue.size() > 0) {
				while (!queue.isEmpty()) {
					int connectCom = queue.poll();
					if (!visited[connectCom]) {
						visited[connectCom] = true;
						needVisit.offer(connectCom);
					}
				}
			}
		}
	}
}

 

옛날에 제출했던 코드가 재채점 되었을 때 결과로 런타임 에러(NullPointer) 를 받은 걸 확인할 수 있었는데 아마 1번 컴퓨터에 연결되어 있는 컴퓨터가 없는 형태의 입력이 들어왔을 때 연결되어 있는 컴퓨터를 표현하는 자료구조 queue 가 비어있는데 queue 에서 데이터를 꺼내는 코드가 동작해버리는 바람에 NullPointer 에러가 발생한게 아닐까 싶다.

특정 시작노드를 기준으로 그래프에서 얼마나 많은 노드들이 연결되어 있는지 확인하는 문제이므로 그래프 탐색 문제에 해당된다.