2606 바이러스

 

 

 

 

 

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

2606번: 바이러스

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int M;
	static int link[][];
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		link = new int[N+1][N+1];
		
		for(int i =0 ; i<M ; i++ ) {
		
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s, " ");
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		link[a][b] = 1;
		link[b][a] = 1;
		
		}
		int answer = bfs(1);
		System.out.println(answer);
	}
	
	public static int bfs(int start) {
		
		Queue<Integer> q = new LinkedList<>();
		int check[] = new int[N+1];
		int count = 0;
		
		check[start]=1;
		q.offer(start);
	
		while(!q.isEmpty()) {
			
			int x = q.poll();
			
			for( int i=0; i<N+1; i++) {
				if(link[x][i]==1 && check[i]!=1) {
					q.offer(i);
					check[i]=1;
					count++;
				}
			}	
		}
		return count;
	}
}

 

bfs로 풀어본 방식이다.

 

N = 컴퓨터 개수

M = 네트워크 상에서 직접 연결된 컴퓨터 쌍의 수

link 배열 = 네트워크 상에서 연결된 컴퓨터들은 1로 채워넣었다.

(만약 1번 컴퓨터, 2번 컴퓨터가 연결되어 있다면, link[1][2] =1 & link[2][1] =1)

 

이렇게 하면 문제에 나온 예제에서는,

1,2

2,3

1,5

5,2

5,6

4,7

컴퓨터들이 연결되어 있기 때문에

 

link 배열에서

link[1][2] =1 & link[2][1] =1

link[2][3] =1 & link[3][2] =1

link[1][5] =1 & link[5][1] =1

link[5][2] =1 & link[2][5] =1

link[5][6] =1 & link[6][5] =1

link[4][7] =1 & link[7][4] =1

이고 나머지는 모두 0 이다.

 

Main 메서드에서 위 상태를 만든뒤 bfs(1) 을 실행한다.

 

그러면 start = 1 인 상태로 진행된다.

Queue (큐)를 만든 뒤 진행하는데,

count 변수는 0으로 초기 설정되어 컴퓨터가 연결되어 있다면 1증가시킨다.

(연결되어 있다면 바이러스에 감염되고, 문제에서 바이러스에 감염되는 컴퓨터 수를 출력하라고 했으므로

결과적으로 count 변수 값이 출력됨)

예를 들어 1번 컴퓨터는 위의 예제에서 2번 컴퓨터와 연결되어 있다.

따라서 link[1][2]=1 이므로,count 값이 증가될 것이다.

하지만 그 후에 link[2][1] 도 검사하게 되는데, 이 경우 역시 값이 1이다. 하지만 이때는 이미

link[1][2] 에서 count 값을 증가시켰기 때문에 여기서는 증가시키면 안된다.

따라서 check 배열을 사용해서, link[1][2] 에서 count 값을 1증가시키면서

check[2] =1 로 만들어주고, link[2][1] =1 이더라도 check[2] 값이 1이기 때문에 이경우는 count 값을 증가시키지 않도록 하는 것이다.

 

------------------------------------

 

자세히 살펴보자면 아래와 같다.

 

link 배열이

link[1][2] =1 & link[2][1] =1

link[2][3] =1 & link[3][2] =1

link[1][5] =1 & link[5][1] =1

link[5][2] =1 & link[2][5] =1

link[5][6] =1 & link[6][5] =1

link[4][7] =1 & link[7][4] =1

이고 나머지는 모두 0 인 상태에서 

bfs(1) 이 진행된다.

 

 

check[1] =1 

 

-------------------------------------- x=1

q에다가 1 넣음  -> q :1

 

while 문으로 들어와서

x=1

 

for 문으로 들어와서

i=0,1,2,3,4,5,6,7 까지

link[1][0] == 1 인지, check[0] != 1 인지 체크 -> x

link[1][1] == 1 인지, check[1] != 1 인지 체크 -> x

link[1][2] == 1 인지, check[2] != 1 인지 체크 -> o

 

이 때, q에다가 2를 집어넣는다. -> q: 2

check[2] = 1

count = 1

 

link[1][3] == 1 인지, check[3] != 1 인지 체크 -> x

link[1][4] == 1 인지, check[4] != 1 인지 체크 -> x

link[1][5] == 1 인지, check[5] != 1 인지 체크 -> o

 

이 때, q에다가 5를 집어넣는다. -> q: 2, 5

check[5] = 1

count = 2

 

... 7까지 진행

 

------------------------------------- x=2

 

이제 다시 while 문으로 와서 q에서 제일 앞에 있는 값인 2를 꺼낸다.

 

그 다음 for 문에서 i=0,1,2,3,4,5,6,7

 

link[2][0] == 1 인지, check[0] != 1 인지 체크 -> x

link[2][1] == 1 인지, check[1] != 1 인지 체크 -> x

 

link[2][1] == 1 이 맞지만, check[1] =1 이므로 여기서는 count 값이 증가되지 않는다.

 

때문에 check 배열이 필요한 것이다.

 

이런식으로 진행하면 count 값을 얻을 수 있다.

 

 

-------------------------------------

 

이렇게 진행해보며, 뭔가 link[1][2] == 1 인지 체크한 뒤,

나중에 또 link[2][1] == 1 인지 체크하는게 번거로워 보였다.

차라리 dfs 를 이용한 다면 더 효과적일 것 같다는 생각이 들었다.

 

 

 

 

 

 

참고 자료 : 

 

https://fbtmdwhd33.tistory.com/28

[백준,BOJ 2606] 바이러스(JAVA 구현,추가풀이)