백준 S3 2606 : 바이러스 🅾️

[문제]

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

 

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

 

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

 

2606번: 바이러스

 

[풀이]

소요시간 : 13분

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int computer=Integer.parseInt(br.readLine());
		List<Integer>[] list=new ArrayList[computer];
		for(int i=0;i<computer;i++) {
			list[i]=new ArrayList<>();
		}
		
		int connect=Integer.parseInt(br.readLine());
		for(int i=0;i<connect;i++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken())-1;
			int y=Integer.parseInt(st.nextToken())-1;
			list[x].add(y);
			list[y].add(x);
		}
		
		int cnt=0;
		boolean[] check=new boolean[computer];
		Queue<Integer> queue=new LinkedList<>();
		queue.add(0);
		check[0]=true;
		
		while(!queue.isEmpty()) {
			int target=queue.poll();
			cnt+=1;
			
			List<Integer> tmp=list[target];
			for(int i=0;i<tmp.size();i++) {
				int num=tmp.get(i);
				if(!check[num]) {
					queue.add(num);
					check[num]=true;
				}
			}
		}
		
		System.out.println(cnt-1);
	}

}

 

이전에 dfs로 풀어본 적이 있는 문제라 빠르게 풀 수 있었던 문제.

풀이를 해보자면..

int computer=Integer.parseInt(br.readLine());
List<Integer>[] list=new ArrayList[computer];
for(int i=0;i<computer;i++) {
	list[i]=new ArrayList<>();
}

 

먼저 컴퓨터의 수를 받아 List<Integer> 형태의 배열을 생성했다.

다음 각 배열을 new ArrayList로 list를 생성해주었다. (그래야 나중에 값을 바로 넣을 수 있기 때문!)

int connect=Integer.parseInt(br.readLine());
for(int i=0;i<connect;i++) {
	StringTokenizer st=new StringTokenizer(br.readLine());
	int x=Integer.parseInt(st.nextToken())-1;
	int y=Integer.parseInt(st.nextToken())-1;
	list[x].add(y);
	list[y].add(x);
}

 

연결된 개수를 입력받고 for 문을 통해 입력값을 받았다.

다음 StringTokenizer를 활용하여 두 수를 x, y로 받고, x번째 인덱스에 y를 넣고 y번째 인덱스에 x를 넣었다.

int cnt=0;
boolean[] check=new boolean[computer];
Queue<Integer> queue=new LinkedList<>();
queue.add(0);
check[0]=true;

 

bfs를 시작하기 전 필요한 것을 선언해주었다.

먼저 수를 세기 위한 cnt, 각 인덱스를 방문했는지 확인하기 위한 boolean 타입의 배열 check를 선언했다.

다음 queue를 사용하고, 맨 처음은 1부터 시작할 것이기 때문에 첫 번째 수를 queue에 넣어준다.

(나는 0부터 시작하도록 해놓아서 0을 add했다)

0은 이제 방문한 인덱스이기 때문에 check[0]을 true로 값을 변경해주었다.

while(!queue.isEmpty()) {
	int target=queue.poll();
	cnt+=1;
			
	List<Integer> tmp=list[target];
	for(int i=0;i<tmp.size();i++) {
		int num=tmp.get(i);
		if(!check[num]) {
			queue.add(num);
			check[num]=true;
		}
	}
}

 

마지막으로 이 문제의 핵심인 bfs를 구현한 코드이다.

queue에서 poll한 수를 target으로 잡고 해당 target 인덱스의 list를 돌며 queue에 수를 넣는다.

이때 check를 통해 값이 true인 수는 이미 지난 수기 때문에 넣지 않는다.

그러면서 cnt를 돌면 1을 포함하여 지난 수들의 개수가 나온다.

그렇기 때문에 최종적으로 cnt-1을 출력해주면 끝. (1을 포함하면 안되므로)

 

그런데 참고로 List 형태의 배열은,

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

 

이런 컴파일러 경고가 생긴다. 이유는 ArrayList를 raw 타입으로 사용했기 때문이다.

이 문제를 해결하기 위해 List를 배열 타입이 아닌 List<List<Integer>>로 다시 시작해서 코드를 작성해보았다.

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int computer=Integer.parseInt(br.readLine());
		List<List<Integer>> list=new ArrayList<>();
		for(int i=0;i<computer;i++) {
			list.add(new ArrayList<>());
		}
		
		int connect=Integer.parseInt(br.readLine());
		for(int i=0;i<connect;i++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken())-1;
			int y=Integer.parseInt(st.nextToken())-1;
			list.get(x).add(y);
			list.get(y).add(x);
		}
		
		int cnt=0;
		boolean[] check=new boolean[computer];
		Queue<Integer> queue=new LinkedList<>();
		queue.add(0);
		check[0]=true;
		
		while(!queue.isEmpty()) {
			int target=queue.poll();
			cnt+=1;
			
			List<Integer> tmp=list.get(target);
			for(int i=0;i<tmp.size();i++) {
				int num=tmp.get(i);
				if(!check[num]) {
					queue.add(num);
					check[num]=true;
				}
			}
		}
		
		System.out.println(cnt-1);
	}

}

 

변경한 코드이다. 결과는 크게 다를 게 없었다.

 

오늘의 코테 끄읕.