백준 2606: 바이러스

문제 2606번: 바이러스

 

먼저 입력받은 그래프를 인접 행렬로 구현해야한다.

인접 행렬로 구현하는 방법은 아래를 참고했다.

https://bamtory29.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84-%EA%B5%AC%ED%98%84-1-%EC%9D%B8%EC%A0%91-%ED%96%89%EB%A0%AC%EB%A1%9C-%EA%B7%B8%EB%9E%98%ED%94%84-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

그래프 구현 1 - 인접 행렬로 그래프 구현하기

인접 행렬로 그래프를 구현하면 아래와 같은 모양일 것이다.

인접 행렬로 그래프를 구현한 모양

 

인접 행렬에서 전체 탐색을 해야하기 때문에 DFS, BFS 알고리즘을 사용하면 된다.

DFS, BFS알고리즘은 아래 영상에 잘 정리되어있다.

https://www.youtube.com/watch?v=_hxFgg7TLZQ&t=627s

 

이를 이용해서 작성한 코드

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

public class Main {

	static boolean[] check;
	static int[][] arr;
	static int count = 0;
	static int node, line;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		node = Integer.parseInt(br.readLine());
		line = Integer.parseInt(br.readLine());

		// 편의를 위해 배열의 1번 인덱스부터 사용 (0번 인덱스 사용 안함)
		arr = new int[node + 1][node + 1]; // 인접 행렬 구현을 위한 배열
		check = new boolean[node + 1]; // 탐색 여부를 알기위한 플래그 배열

		// 인접 행렬 그래프 구현
		for (int i = 0; i < line; i++) {
			StringTokenizer str = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());

			arr[a][b] = arr[b][a] = 1;
		}

		// 깊이 우선 탐색
		dfs(1);

		// 첫 번째 컴퓨터인 1의 count를 빼줘야 함
		System.out.println(count - 1);

	}

	// 깊이 우선 탐색
	public static void dfs(int start) {
		check[start] = true;
		count++;

		// 그래프 탐색: 인접해있고 체크하지 않은 노드 탐색
		for (int i = 0; i <= node; i++) {
			if (arr[start][i] == 1 && !check[i])
				dfs(i);
		}

	}

}