[ALGO#4] 백준_2606_실버3_바이러스 : DFS [JAVA]

문제링크 : https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

전형적인 DFS 기본 문제였다.

그래프의 간선 연결을 2차원 배열에 표시하여 DFS로 표시된 곳을 탐색하고 방문 처리해줬다.

바이러스가 1번부터 점염되서 DFS에 인자를 1부터 시작해줬다.

출력할 때는 처음 감염시킨 1번 컴퓨터는 제외라고 문제에 적혀 있어서 answer-1을 해줬다.

 

 

성능 요약

메모리: 11612 KB, 시간: 76 ms

분류

그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)

 

전체코드 (자바)

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

public class Main {
	static boolean arr[][];
	static boolean[] visited;
	static int N;
	static int answer;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int connected = Integer.parseInt(br.readLine());
		// 연결되어있는 것을 알아야 하니깐
		arr = new boolean [N+1][N+1];
		visited = new boolean[N+1];
		StringTokenizer st;
		
		// 1. 그래프 정보 입력
		for (int i = 1; i <= connected; i++) {
			st = new StringTokenizer(br.readLine());	
			int cpu1 = Integer.parseInt(st.nextToken());
			int cpu2 = Integer.parseInt(st.nextToken());
			arr[cpu1][cpu2] = arr[cpu2][cpu1] = true;
		}
		// 2. dfs 및 결과 출력
		dfs(1);
		 // 1번 컴퓨터는 문제에서 카운팅 제외하라고 나왔음
		System.out.println(answer-1);		
	}
	private static void dfs(int idx) {
		answer++;
		// 방문 체크
		visited[idx] = true;
		// for문 N대신 arr.length 넣으면 ArrayIndexOutOfBoundsException: 8
		// dfs 방문 탐색
		for (int i = 1; i <= N; i++) {
			// 방문 안 했고 간선이 연결되어 있으면(=2차원 베열에 표시) dfs 진행
			if(!visited[i] && arr[idx][i]) {
				dfs(i); 
			}
		}
	}
}