java - 백준 알고리즘 - 2606 바이러스

알고리즘 분류에는 플로이드 와샬 알고리즘이라고 분류 되어있지만 dfs를 이용해서 풀었다.

 

자세한 설명은 코드에 주석을 보면 좋을 것 같다.

 

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

public class Main {

	static int N, M, result;
	static boolean[][] conn;	// 컴퓨터 간의 연결을 나타내기 위한 배열
	static boolean[] visited;	// 방문을 체크하기 위한 배열

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

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

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		conn = new boolean[N + 1][N + 1];
		visited = new boolean[N + 1];

		for (int i = 1; M >= i; ++i) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			int first = Integer.parseInt(st.nextToken());
			int second = Integer.parseInt(st.nextToken());
			conn[first][second] = true;
			conn[second][first] = true;
		}		// 1 과 2가 연결 되어 있다는 것은 2와 1도 연결 되는것.

		dfs(1);
		System.out.println(result);

	}

	static void dfs(int start) {
		visited[start] = true;	// 방문 처리 
		for (int i = 1; N >= i; ++i) {	// 모든 컴퓨터를 돌면서 
        								// 연결된 컴퓨터이면서 방문하지 않은 컴퓨터를 확인
			if (conn[start][i] == true && visited[i] == false) {
					result++;	// 조건에 해당되면 +1 
					dfs(i);		// 조건에 해당되는 컴퓨터를 기준으로 반복
				}
			}
		}

}