[BAEKJOON] 2606번 바이러스

---

이차원배열에 인접된 컴퓨터 번호를 인덱스로 간주하여 연결된 컴퓨터들은 모두 1로 채운다.

이차원배열을 이용할 때 arr[][] 배열이 있을 때 컴퓨터 1번과 2번이 연결된 것을 표현하기 위해서는 아래와 같이 인접행렬 방식으로 행과 열의 인덱스를 바꿔도 연결된 것을 알 수 있도록 한다.

1번과 2번이 연결됐다 == 2번과 1번이 연결됐다

arr[1][2] = 1;
arr[2][1] = 1;

인덱스 1(1번 컴퓨터)를 시작으로 연결된 컴퓨터를 찾는다면 해당 컴퓨터와 연결된 또 다른 컴퓨터를 찾기 위해 큐에 저장한다.

큐가 텅 빌 때까지 반복하며 연결된 컴퓨터를 찾아 개수를 센다.

모든 연결된 컴퓨터의 개수를 찾는 것이 아닌, 1번 컴퓨터와의 연결관계만 확인하면 되기 때문에 bfs()를 호출할 때 매개인자로 1을 넣어주면 된다.

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 arr[][];
	static boolean visited[];
	static int cnt, N, TC;
	static int dx[] = {0,0,-1,1};
	static int dy[] = {1,-1,0,0};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1][N+1];
		visited = new boolean[N+1];
		TC = Integer.parseInt(br.readLine());
		for(int i=0; i<TC; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr[x][y] = 1;
			arr[y][x] = 1;
		}
		bfs(1); // 1과 연결된 컴퓨터부터 bfs 탐색 시작
		System.out.println(cnt);
	}
	static void bfs(int x) {
		Queue<Integer> q = new LinkedList<>();
		q.add(x);
		visited[x] = true;
		
		while(!q.isEmpty()) {
			int now = q.poll(); // 큐에 저장된 포인트 꺼내기
						
			for(int i=1; i<=N; i++) {
								
				if((arr[now][i]==1 && !visited[i])) {
					visited[i] = true;
					q.add(i);
					cnt++;
				}
			}
		}
	}
}

[출처]

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

2606번: 바이러스