/ BOJ

BOJ_2060_바이러스_JAVA

문제 : 바이러스

링크 : BOJ_2060_바이러스

접근 방식

DFS 또는 BFS를 이용하여 인접한 노드를 전체 순회하고 카운트 하면 되는 문제이다. 그래프 생성과 DFS, BFS중 한 가지라도 구현할 수 있다면 문제를 풀 수 있다.

풀이 방법

  1. 인접 행렬을 통해 주어진 인접 상태 좌표를 읽어들여 그래프를 구현한다.

  2. DFS를 이용하여 인접 노드를 순회한다. DFS는 재귀로 구현한다. 먼저, 해당 노드를 방문처리한다.

  3. 배열의 크기만큼 반복하는데, 해당 노드의 행에 아직 방문하지 않은 상태의 인접한 노드가 있다면, 해당 노드를 방문처리하고 재귀함수를 호출한다. 그리고 카운트를 1 증가시킨다.

  4. 모든 순회가 끝나면 저장된 카운트 값을 출력한다.

소스 코드


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

public class BOJ_2060_바이러스 {
	static int N;
	static int cnt;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


		N = Integer.parseInt(in.readLine());

		int C = Integer.parseInt(in.readLine());

		int[][] arr = new int[N+1][N+1];
		StringTokenizer st;
		for(int i=0;i<C;i++) {
			st = new StringTokenizer(in.readLine()," ");

			int from = Integer.parseInt(st.nextToken());

			int to = Integer.parseInt(st.nextToken());
			arr[from][to] = 1;
			arr[to][from] = 1;

		}

		dfs(arr,new boolean[N+1],1);


		System.out.println(cnt);
//		for(int i=1;i<=N;i++) {
//			System.out.println(Arrays.toString(arr[i]));
//		}

	}

	public static void dfs(int[][] arr, boolean[] isVisited, int V) {
		isVisited[V] = true;

		for(int i=1;i<=N;i++) {
			if(!isVisited[i] && arr[V][i] == 1) {
				cnt++;
				dfs(arr, isVisited, i);
			}
		}

	}

}