[2606] 바이러스

간단한 bfs/dfs 문제

 

컴퓨터의 연결 관계를 2차원배열로 선언하고, 양방향 관계인 것을 고려하면 쉽게 풀 수 있다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	// 지나온 곳 체크하기 위한 변수
	public static int[] checked;
    // 컴퓨터 네트워크 관계 저장 변수
	public static int[][] rel;
    //dfs를 위한 결과값 변수
	public static int cnt = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int com = sc.nextInt();
		checked = new int[com + 1];
		rel = new int[com + 1][com + 1];
		int n = sc.nextInt();

		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
            // 양방향 관계를 위해 다음과 같이 저장
			rel[x][y] = 1;
			rel[y][x] = 1;
		}

		// System.out.println(bfs());

		dfs(1);
		System.out.println(cnt);
	}

	public static int bfs() {
		int result = 0;

		Queue<Integer> q = new LinkedList<>();
		q.add(1);
		checked[1] = 1;

		while (!q.isEmpty()) {
			int now = q.poll();

			for (int i = 2; i < checked.length; i++) {
				if (rel[now][i] == 1 && checked[i] != 1) {
					checked[i] = 1;
					result++;
					q.add(i);
				}
			}
		}

		return result;
	}

	public static void dfs(int a) {
		checked[a] = 1;

		for (int i = 1; i < checked.length; i++) {
			if (rel[a][i] == 1 && checked[i] != 1) {
				cnt++;
				dfs(i);
			}
		}
	}
}