[BOJ] 2606. 바이러스

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력

4

코드

package _00_TodayProblem.tp03._00_inflearn._03_2606;

import java.util.*;
import java.io.*;

public class Solution {
	static boolean[][] graph;
	static boolean[] visited;
	static int N, M;
	static int answer;

	// 4) dfs 구현
	public static void dfs(int idx) {
		visited[idx] = true;
        answer++;

		for (int i = 1; i <= N; i++) {
			if (visited[i] == false && graph[idx][i]) {
				dfs(i);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		// 0. 입력과 초기화
		System.setIn(new FileInputStream("src/_00_TodayProblem/tp03/_00_inflearn/_03_2606/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

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

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

		// 1. graph에 연결 정보 채우기
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			graph[x][y] = true;
			graph[y][x] = true;
		}

		// 2. dfs(재귀함수) 호출
		dfs(1);

		// 3. 출력
		bw.write(String.valueOf(answer - 1));
		br.close();
		bw.close();		
	}
}

풀이

💡초기화
1번 컴퓨터부터 7번 컴퓨터까지 있기 때문에 인덱스에는 +1을 해야합니다.
이는 예제 입력값을 보면 이해하기 더 쉽습니다. 따라서,

• graph = new boolean[N + 1][N + 1];
• visited = new boolean[N + 1];

💡graph에 연결 정보 채우기

• 컴퓨터 쌍의 수 즉, 간선의 갯수만큼 graph에 채워야합니다.
• StringTokenizer로 값을 받아와 타입에 맞춰 변수에 담아줍니다.
• 받아온 x와 y 값은 간선으로 이어진 두 정점이며,
• graph[x][y] = true; & graph[y][x] = true;
  • x정점기준으로 연결된 y정점과 y정점기준으로 연결된 x정점을 의미합니다..
  • 만약 graph[x][y] = true;만 있고, 입력값이 2 1이라고 들어오면
    • dfs(1)일 때 1 2가 없기 때문에 재귀함수가 바로 종료됩니다..

💡dfs 호출과 출력

• 1번 컴퓨터부터 시작한다고 했으니 dfs(1)
• BufferedWriter를 사용하여 문자열 출력

💡dfs 구현

• 1번 컴퓨터에서 시작하니 visited[1] = true;가 됩니다.
• 재귀가 진행될 때마다 방문한 컴퓨터의 갯수가 하나씩 증가하게 됩니다. answer++;
• visited[i] == false && graph[idx][i]
  • visited[i]
    • 방문 여부를 따지는 배열입니다.
  • graph[idx][i]
    • idx라는 정점과 i라는 정점이 연결되어있는지 확인합니다.
    • 이는 연결 정보 채우기에서 값을 true로 채운 값들이 조건이 됩니다.
• idx = 1이 들어왔을 때 visited[1] = true;가 되며,
• i = 1일 때 visited[1] == false 조건을 만족하지 못해 다음 반복문으로 넘어갑니다.
• i = 2일 때 visited[2] == false && graph[1][2]는 성립합니다.
• 따라서, dfs(2)를 호출하게 되면서 2번 컴퓨터를 방문하게 됩니다.
• 이 때 함수가 재귀되면서, visited[2] = true로 방문했다는 점을 남깁니다.