[백준/자바] 2606번: 바이러스

문제

https://www.acmicpc.net/problem/2606

풀이

• 한 컴퓨터가 웜 바이러스에 걸리면 네트워크 상에서 연결되어 있는 모든 컴퓨터가 웜 바이러스에 걸리게 됨
• 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 바이러스에 거릴게 되는 컴퓨터의 수 출력

전형적인 그래프 탐색 문제입니다.
DFS와 BFS 풀이를 모두 가져왔습니다.

공통적으로 하는 입력 부분입니다.

		v = Integer.parseInt(br.readLine());
		e = Integer.parseInt(br.readLine());
		
		graph = new ArrayList<>();
		for (int i = 0; i <= v; i++) graph.add(new ArrayList<>());
		
		for (int i = 0; i < e; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

• 그래프는 인접 리스트로 구현하였습니다.
• 노드 a와 b 모두 입력을 받고 무방향 그래프이므로, 양쪽으로 값을 추가했습니다.

먼저 DFS 코드부터 설명하겠습니다.

	private static void dfs(int x) {
		visited[x] = true; // 탐색을 시작하는 노드 방문 처리
		
		for (int nxt : graph.get(x)) { // 인접한 다음 노드 탐색
			if (!visited[nxt]) { // 방문하지 않은 노드라면
				dfs(nxt); // 재귀
				answer++; // 시행 횟수 증가(연결된 노드의 수++)
			}
		}
	}

• 연결된 노드의 수만 탐색하면 되므로, 굉장히 간결합니다.
• dfs를 실행할 때마다 값을 증가시켜 주면, 연결된 노드의 수를 알 수 있습니다.

다음으로 BFS 코드입니다.

	private static void bfs() {
		visited[1] = true; // 시작 노드 방문 처리
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(1); // 큐에 값 삽입
		
		while (!queue.isEmpty()) {
			int cur = queue.poll(); // 큐 가장 앞에 있는 값 추출
			
			for (int nxt : graph.get(cur)) { // 인접한 다음 노드 탐색
				if (!visited[nxt]) { // 방문하지 않은 노드라면?
					visited[nxt] = true; // 방문 처리
					queue.add(nxt); // 큐에 삽입
					answer++; // 연결된 노드의 수++
				}
			}
		}
	}

• 아주 전형적인 BFS 코드입니다.
• 현재 노드에서 인접한 노드들 중, 방문하지 않은 노드가 있으면 큐에 넣고 탐색을 이어 가주면 됩니다.

코드(DFS)

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

public class Main_2606_dfs {
	static int v, e;
	static boolean[] visited;
	static List<ArrayList<Integer>> graph;
	
	static int answer = 0;
	
	private static void dfs(int x) {
		visited[x] = true;
		
		for (int nxt : graph.get(x)) {
			if (!visited[nxt]) {
				dfs(nxt);
				answer++;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		v = Integer.parseInt(br.readLine());
		e = Integer.parseInt(br.readLine());
		
		graph = new ArrayList<>();
		for (int i = 0; i <= v; i++) graph.add(new ArrayList<>());
		
		for (int i = 0; i < e; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		
		visited = new boolean[v+1];
		dfs(1);
		
		System.out.println(answer);
	}

}

코드(BFS)

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

public class Main_2606_bfs {
	static int v, e;
	static boolean[] visited;
	static List<ArrayList<Integer>> graph;
	
	static int answer = 0;
	
	private static void bfs() {
		visited[1] = true;
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(1);
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			
			for (int nxt : graph.get(cur)) {
				if (!visited[nxt]) {
					visited[nxt] = true;
					queue.add(nxt);
					answer++;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		v = Integer.parseInt(br.readLine());
		e = Integer.parseInt(br.readLine());
		
		graph = new ArrayList<>();
		for (int i = 0; i <= v; i++) graph.add(new ArrayList<>());
		
		for (int i = 0; i < e; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
        
		visited = new boolean[v+1];
		bfs();
		
		System.out.println(answer);
	}

}